Results 51 to 60 of about 8,457 (169)
Ramsey Numbers of Connected Clique Matchings
The Electronic Journal of Combinatorics, 2017 We determine the Ramsey number of a connected clique matching. That is, we show that if $G$ is a $2$-edge-coloured complete graph on $(r^2-r-1)n-r+1$ vertices, then there is a monochromatic connected subgraph containing $n$ disjoint copies of $K_r$, and that this number of vertices cannot be reduced.
openaire +4 more sources
Clique roots of K4-free chordal graphs
Electronic Journal of Graph Theory and Applications, 2019 The clique polynomial C(G, x) of a finite, simple and undirected graph G = (V, E) is defined as the ordinary generating function of the number of complete subgraphs of G. A real root of C(G, x) is called a clique root of the graph G.
Hossein Teimoori Faal
doaj +1 more source
Intersection graphs associated with semigroup acts [PDF]
Categories and General Algebraic Structures with Applications, 2019 < p>The intersection graph $\\mathbb{Int}(A)$ of an $S$-act $A$ over a semigroup $S$ is an undirected simple graph whose vertices are non-trivial subacts of $A$, and two distinct vertices are adjacent if and only if they have a non-empty intersection. In
Abdolhossein Delfan +2 more
doaj +1 more source
Treewidth versus clique number. II. Tree-independence number
Journal of Combinatorial Theory, Series BIn 2020, we initiated a systematic study of graph classes in which the treewidth can only be large due to the presence of a large clique, which we call $(\mathrm{tw},ω)$-bounded. While $(\mathrm{tw},ω)$-bounded graph classes are known to enjoy some good algorithmic properties related to clique and coloring problems, it is an interesting open problem ...
Dallard, Clément +2 more
openaire +2 more sources
Hypergraph Ramsey numbers: Triangles versus cliques
Journal of Combinatorial Theory, Series A, 2013 Abstract A celebrated result in Ramsey Theory states that the order of magnitude of the triangle-complete graph Ramsey numbers R ( 3 , t ) is t 2 / log t . In this paper, we consider an analogue of this problem for uniform hypergraphs. A triangle is a hypergraph consisting of edges e , f , g such that | e ∩
Alexandr Kostochka +2 more
openaire +1 more source
Recognition of Unipolar and Generalised Split Graphs
Algorithms, 2015 A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar.
Colin McDiarmid, Nikola Yolov
doaj +1 more source
The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
Algorithms, 2020 Let G=(V,E) be an undirected graph with vertex set V and edge set E. A clique C of G is a subset of the vertices of V with every pair of vertices of C adjacent. A maximum clique is a clique with the maximum number of vertices. A tabu search algorithm for
Derek H. Smith +2 more
doaj +1 more source
Clique numbers of graph unions
, 2013 Let $B$ and $R$ be two simple graphs with vertex set $V$, and let $G(B,R)$ be the simple graph with vertex set $V$, in which two vertices are adjacent if they are adjacent in at least one of $B$ and $R$. For $X \subseteq V$, we denote by $B|X$ the subgraph of $B$ induced by $X$; let $R|X$ and $G(B,R)|X$ be defined similarly. We say that the pair $(B,R)$
Chudnovsky, Maria, Ziani, Juba
openaire +2 more sources
Extremal digraphs with given clique number
Linear Algebra and its Applications, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Drury, S. W., Lin, Huiqiu
openaire +1 more source
Packing chromatic number versus chromatic and clique number [PDF]
Aequationes mathematicae, 2017 The packing chromatic number $ _ (G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$, $i\in [k]$, where each $V_i$ is an $i$-packing. In this paper, we investigate for a given triple $(a,b,c)$ of positive integers whether there exists a graph $G$ such that $ (G) = a$, $ (G) = b$, and $
Boštjan Brešar +3 more
openaire +3 more sources