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     

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     

On triangles in ‐minor free graphs

We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (K₆ and K₇, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a K₈‐minor or contains K_{2, 2, 2, 2, 2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K₇‐minor free graph is 8‐colorable and every K₈‐minor free graph is 10‐colorable.     

Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs

An edge‐coloring of a graph G with colors is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erd?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erd?s's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.     

6‐Star‐Coloring of Subcubic Graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2‐colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6‐star‐colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed (J Graph Theory 47(3) (2004), 140–153).     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper k‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors, and the question is whether there is a proper edge coloring where every edge receives a color from its list. We show that both problems are NP‐complete on (a) planar 3‐regular bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite series‐parallel graphs. This improves previous results of Easton and Parker 6 , and Fiala 8 . © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 313–324, 2005     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

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.     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V₁ and V₂ such that in G[V₁] every vertex has degree at most k, while G[V₂] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

Planar graphs without 4‐cycles are acyclically 6‐choosable

A proper vertex coloring of a graph G=(V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L={L(v)|v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this paper we prove that every planar graph G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009     

(2 + ϵ)‐Coloring of planar graphs with large odd‐girth

The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000