A new upper bound on the cyclic chromatic number

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^c. Let Δ^* be the maximum face degree of a graph. There exist plane graphs with χ^c = ?3/2 Δ^*?. Ore and Plummer [ 5 ] proved that χ^c ≤ 2, Δ^*, which bound was improved to ?9/5, Δ^*? by Borodin, Sanders, and Zhao [ 1 ], and to ?5/3,Δ^*? by Sanders and Zhao [ 7 ]. We introduce a new parameter k^*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ^c ≤ max {Δ^* + 3,k^* + 2, Δ^* + 14, 3, k^* + 6, 18}, and if Δ^* ≥ 4 and k^* ≥ 4, then χ^c ≤ Δ^* + 3,k^* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

New upper bounds for the chromatic number of a graph*

We show that for any graph G, the chromatic number χ(G) ≤ Δ₂(G) + 1, where Δ₂(G) is the largest degree that a vertex ν can have subject to the condition that ν is adjacent to a vertex whose degree is at least as big as its own. Moreover, we show that the upper bound is best possible in the the following sense: If Δ₂(G) ≥ 3, then to determine whether χ(G) ≤ Δ₂(G) is an NP‐complete problem. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 117–120, 2001     

Circular chromatic index of graphs of maximum degree 3

This paper proves that if G is a graph (parallel edges allowed) of maximum degree 3, then χ′_c(G) ≤ 11/3 provided that G does not contain H₁ or H₂ as a subgraph, where H₁ and H₂ are obtained by subdividing one edge of K (the graph with three parallel edges between two vertices) and K₄, respectively. As χ′_c(H₁) = χ′_c(H₂) = 4, our result implies that there is no graph G with 11/3 < χ′_c(G) < 4. It also implies that if G is a 2‐edge connected cubic graph, then χ′_c(G) ≤ 11/3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 325–335, 2005     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010     

Circular choosability of graphs

This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) χ_{c, l}(G) of a graph G and prove that they are equivalent. Then we prove that for any graph G, χ_{c, l}(G) ≥ χ_l(G) ? 1. Examples are given to show that this bound is sharp in the sense that for any ? 0, there is a graph G with χ_{c, l}(G) > χ_l(G) ? 1 + ?. It is also proved that k‐degenerate graphs G have χ_{c, l}(G) ≤ 2k. This bound is also sharp: for each ? < 0, there is a k‐degenerate graph G with χ_{c, l}(G) ≥ 2k ? ?. This shows that χ_{c, l}(G) could be arbitrarily larger than χ_l(G). Finally we prove that if G has maximum degree k, then χ_{c, l}(G) ≤ k + 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 210–218, 2005     

Edge‐partitions of planar graphs and their game coloring numbers

Let G be a planar graph and let g(G) and Δ(G) be its girth and maximum degree, respectively. We show that G has an edge‐partition into a forest and a subgraph H so that (i) Δ(H) ≤ 4 if g(G) ≥ 5; (ii) Δ(H) ≤ 2 if g(G) ≥ 7; (iii) Δ(H)≤ 1 if g(G) ≥ 11; (iv) Δ(H) ≤ 7 if G does not contain 4‐cycles (though it may contain 3‐cycles). These results are applied to find the following upper bounds for the game coloring number col_g(G) of a planar graph G: (i) col_g(G) ≤ 8 if g(G) ≥ 5; (ii) col_g(G)≤ 6 if g(G) ≥ 7; (iii) col_g(G) ≤ 5 if g(G) ≥ 11; (iv) col_g(G) ≤ 11 if G does not contain 4‐cycles (though it may contain 3‐cycles). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 307–317, 2002     

Large induced forests in sparse graphs

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K₄, then a(G) ≥ n ? e/4 ? 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n ? α(G))/(Δ ? 1)². Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001     

Parity vertex coloring of outerplane graphs

A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c, the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G is denoted by χ_p(G).In this paper we prove that χ_p(G)≤12 for every 2-connected outerplane graph G. We show that there is a 2-connected outerplane graph G such that χ_p(G)=10. If a 2-connected outerplane graph G is bipartite, then χ_p(G)≤8, moreover, this bound is best possible.     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Parity vertex colouring of plane graphs

A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χ_p(G).In this paper, we prove that χ_p(G)≤118 for every 2-connected plane graph G.     

Multichromatic numbers,star chromatic numbers and Kneser graphs

We investigate the relation between the multichromatic number (discussed by Stahl and by Hilton, Rado and Scott) and the star chromatic number (introduced by Vince) of a graph. Denoting these by χ* and η*, the work of the above authors shows that χ*(G) = η*(G) if G is bipartite, an odd cycle or a complete graph. We show that χ*(G) ≤ η*(G) for any finite simple graph G. We consider the Kneser graphs , for which χ* = m/n and η*(G)/χ*(G) is unbounded above. We investigate particular classes of these graphs and show that η* = 3 and η* = 4; (n ≥ 1), and η* = m - 2; (m ≥ 4). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 137–145, 1997     

The circular chromatic number of series‐parallel graphs with large girth

It was proved by Hell and Zhu that, if G is a series‐parallel graph of girth at least 2⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series‐parallel graph G of girth 2⌊(3k − 1)/2⌋ − 1 such that χ_c(G) > 4k/(2k − 1). © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 185–198, 2000     

On the diameter of i‐center in a graph without long induced paths

A graph G is said to be P_t‐free if it does not contain an induced path on t vertices. The i‐center C_i(G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, ⌊t/2⌋ ≤ i ≤ t − 2, with the property that, in every connected P_t‐free graph G, the i‐center C_i(G) of G induces a connected subgraph of G. In this article, the sharp upper bound on the diameter of G[C_i(G)] is established for every i ∈ I(t). The sharp lower bound on I(t) is obtained consequently. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 235–241, 1999     

Coloring graphs from lists with bounded size of their union

A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 2^4k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998     

The rainbow connection of a graph is (at most) reciprocal to its minimum degree

An edge‐colored graph Gis rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make Grainbow edge‐connected. We prove that if Ghas nvertices and minimum degree δ then rc(G)<20n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph Gis rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make Grainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if Ghas nvertices and minimum degree δ then rvc(G)<11n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010