Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Bounding the Clique‐Width of H‐Free Chordal Graphs

A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P₄‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K₄‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs.     

On factors of 4‐connected claw‐free graphs*

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001     

Exhaustive generation of k‐critical ‐free graphs

We describe an algorithm for generating all k‐critical ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H‐free, k‐chromatic, and every H‐free proper subgraph of G is ‐colorable). Using this algorithm, we prove that there are only finitely many 4‐critical ‐free graphs, for both and . We also show that there are only finitely many 4‐critical ‐free graphs. For each of these cases we also give the complete lists of critical graphs and vertex‐critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3‐colorability problem in the respective classes. In addition, we prove a number of characterizations for 4‐critical H‐free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4‐critical planar ‐free graphs is finite. We also determine all 52 4‐critical planar P₇‐free graphs. We also prove that every P₁₁‐free graph of girth at least five is 3‐colorable, and show that this is best possible by determining the smallest 4‐chromatic P₁₂‐free graph of girth at least five. Moreover, we show that every P₁₄‐free graph of girth at least six and every P₁₇‐free graph of girth at least seven is 3‐colorable. This strengthens results of Golovach et al.     

Linear Clique‐Width for Hereditary Classes of Cographs

The class of cographs is known to have unbounded linear clique‐width. We prove that a hereditary class of cographs has bounded linear clique‐width if and only if it does not contain all quasi‐threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.     

Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs

We show that if G is a 4‐connected claw‐free graph in which every induced hourglass subgraph S contains two non‐adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 267–276, 2005     

A note on 3‐partite graphs without 4‐cycles

Let $C_4$ be a cycle of order 4. Write $ex\left(n,n,n,C_4\right)$ for the maximum number of edges in a balanced 3‐partite graph whose vertex set consists of three parts, each has $n$ vertices that have no subgraph isomorphic to $C_4$. In this paper, we show that $ex\left(n,n,n,C_4\right)\ge \frac{3}{2}n\left(p+1\right)$, where $n=\frac{p\left(p?1\right)}{2}$ and $p$ is a prime number. Note that $ex\left(n,n,n,C_4\right)\le \left(\frac{3\sqrt{2}}{2}+o\left(1\right)\right)n^{\frac{3}{2}}$ from Tait and Timmons's works. Since for every integer $m$, one can find a prime $p$ such that $m\le p\le \left(1+o\left(1\right)\right)m$, we obtain that $\underset{n\to \infty }{\lim }\frac{ex\left(n,n,n,C_4\right)}{\frac{3\sqrt{2}}{2}{n}^{\frac{3}{2}}}=1$.     

Precoloring extension for K4‐minor‐free graphs

Let G=(V, E) be a graph where every vertex v∈V is assigned a list of available colors L(v). We say that G is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If L(v)={1, …, k} for all v∈V then a corresponding list coloring is nothing other than an ordinary k‐coloring of G. Assume that W?V is a subset of V such that G[W] is bipartite and each component of G[W] is precolored with two colors taken from a set of four. The minimum distance between the components of G[W] is denoted by d(W). We will show that if G is K₄‐minor‐free and d(W)≥7, then such a precoloring of W can be extended to a 4‐coloring of all of V. This result clarifies a question posed in 10. Moreover, we will show that such a precoloring is extendable to a list coloring of G for outerplanar graphs, provided that |L(v)|=4 for all v∈V\W and d(W)≥7. In both cases the bound for d(W) is best possible. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 284‐294, 2009     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

Convex‐round graphs are circular‐perfect

We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round graphs are circular‐perfect, a concept introduced recently by Zhu [10]. Secondly, we characterize maximal K_r‐free convex‐round graphs and show that they can be obtained from certain circular cliques in a simple fashion. Our proofs rely on several structural properties of convex‐round graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 182–194, 2002     

Exponentially many 4‐list‐colorings of triangle‐free graphs on surfaces

Thomassen proved that every planar graph G on n vertices has at least distinct L‐colorings if L is a 5‐list‐assignment for G and at least distinct L‐colorings if L is a 3‐list‐assignment for G and G has girth at least five. Postle and Thomas proved that if G is a graph on n vertices embedded on a surface Σ of genus g, then there exist constants such that if G has an L‐coloring, then G has at least distinct L‐colorings if L is a 5‐list‐assignment for G or if L is a 3‐list‐assignment for G and G has girth at least five. More generally, they proved that there exist constants such that if G is a graph on n vertices embedded in a surface Σ of fixed genus g, H is a proper subgraph of G, and ϕ is an L‐coloring of H that extends to an L‐coloring of G, then ϕ extends to at least distinct L‐colorings of G if L is a 5‐list‐assignment or if L is a 3‐list‐assignment and G has girth at least five. We prove the same result if G is triangle‐free and L is a 4‐list‐assignment of G, where , and .     

Line graphs of multigraphs and Hamilton‐connectedness of claw‐free graphs

We introduce a closure concept that turns a claw‐free graph into the line graph of a multigraph while preserving its (non‐)Hamilton‐connectedness. As an application, we show that every 7‐connected claw‐free graph is Hamilton‐connected, and we show that the well‐known conjecture by Matthews and Sumner (every 4‐connected claw‐free graph is hamiltonian) is equivalent with the statement that every 4‐connected claw‐free graph is Hamilton‐connected. Finally, we show a natural way to avoid the non‐uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152‐173, 2011     

Clique minors in double‐critical graphs

A connected t‐chromatic graph G is double‐critical if is ‐colorable for each edge . A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all . Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K₈ minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

Hamilton connectivity of line graphs and claw‐free graphs

Let G be a graph and let V₀ = {ν∈ V(G): d_G(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V₀| ≤ 29 or G[V₀] contains at most 5 vertex disjoint K₄'s, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Regular 4‐critical graphs of even degree

In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erd?s conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004     

Rank‐width of random graphs

Rank‐width of a graph G, denoted by rw (G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514–528]. We investigate the asymptotic behavior of rank‐width of a random graph G(n, p). We show that, asymptotically almost surely, (i) if p∈(0, 1) is a constant, then rw (G(n, p)) = ?n/3??O(1), (ii) if , then rw (G(n, p)) = ?1/3??o(n), (iii) if p = c/n and c>1, then rw (G(n, p))?rn for some r = r(c), and (iv) if p?c/n and c81, then rw (G(n, p))?2. As a corollary, we deduce that the tree‐width of G(n, p) is linear in n whenever p = c/n for each c>1, answering a question of Gao [2006]. © 2011 Wiley Periodicals, Inc. J Graph Theory.