Acyclic 4-coloring of planar graphs without 4- and 5-cycles

Every planar graph is known to be acyclically 5-colorable (O.V.Borodin, 1976). Some sufficient conditions are also obtained for a planar graph to be acyclically 4- and 3-colorable. In particular, the acyclic 4-colorability was proved for the following planar graphs: without 3- and 4-cycles (O.V.Borodin, A.V. Kostochka, and D.R.Woodall, 1999), without 4-, 5-, and 6-cycles, or without 4-, 5-, and 7-cycles, or without 4-, 5-, and intersecting 3-cycles (M. Montassier, A.Raspaud andW.Wang, 2006), and without 4-, 5-, and 8-cycles (M. Chen and A.Raspaud, 2009). The purpose of this paper is to prove that each planar graph without 4- and 5-cycles is acyclically 4-colorable.     

Acyclic 5-choosability of planar graphs without 4-cycles

The conjecture on the acyclic 5-choosability of planar graphs (Borodin et al., 2002) as yet has been verified only for several restricted classes of graphs: those of girth at least 5 (Montassier, Ochem, and Raspaud, 2006), without 4- and 5-cycles or without 4- and 6-cycles (Montassier, Raspaud, and Wang, 2007), with neither 4-cycles nor chordal 6-cycles (Zhang and Xu, 2009), with neither 4- cycles nor two 3-cycles at distance less than 3 (Chen and Wang, 2008), and with neither 4-cycles nor intersecting 3-cycles (Chen and Raspaud, 2010). Wang and Chen (2009) proved that the planar graphs without 4-cycles are acyclically 6-choosable. We prove that a planar graph without 4-cycles is acyclically 5-choosable, which is a common strengthening of all above-mentioned results.     

Acyclic 3-choosability of planar graphs without cycles of length from 4 to 12

Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (O. V. Borodin et al., 2002). This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4- and 3-colorable. In particular, a planar graph of girth at least 7 is acyclically 3-colorable (O. V. Borodin, A. V. Kostochka and D. R. Woodall, 1999) and acyclically 3-choosable (O. V. Borodin et. al, 2009). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of k-cycles, where 4 ≤ k ≤ S. Here, we prove that every planar graph without cycles of length from 4 to 12 is acyclically 3-choosable.     

Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles

Every planar graph is known to be acyclically 7‐choosable and is conjectured to be acyclically 5‐choosable (O. V. Borodin, D. G. Fon‐Der‐Flaass, A. V. Kostochka, E. Sopena, J Graph Theory 40 (2002), 83–90). This conjecture if proved would imply both Borodin's (Discrete Math 25 (1979), 211–236) acyclic 5‐color theorem and Thomassen's (J Combin Theory Ser B 62 (1994), 180–181) 5‐choosability theorem. However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4‐ and 3‐choosable. In particular, the acyclic 4‐choosability was proved for the following planar graphs: without 3‐, 4‐, and 5‐cycles (M. Montassier, P. Ochem, and A. Raspaud, J Graph Theory 51 (2006), 281–300), without 4‐, 5‐, and 6‐cycles, or without 4‐, 5‐, and 7‐cycles, or without 4‐, 5‐, and intersecting 3‐cycles (M. Montassier, A. Raspaud, W. Wang, Topics Discrete Math (2006), 473–491), and neither 4‐ and 5‐cycles nor 8‐cycles having a triangular chord (M. Chen and A. Raspaud, Discrete Math. 310(15–16) (2010), 2113–2118). The purpose of this paper is to strengthen these results by proving that each planar graph without 4‐ and 5‐cycles is acyclically 4‐choosable.     

Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles

Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002) [7]. This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs.Some sufficient conditions are also obtained for a planar graph to be acyclically 4-choosable and 3-choosable. In particular, acyclic 4-choosability was proved for the following planar graphs: without 3-cycles and 4-cycles (Montassier, 2006 [23]), without 4-cycles, 5-cycles and 6-cycles (Montassier et al. 2006 [24]), and either without 4-cycles, 6-cycles and 7-cycles, or without 4-cycles, 6-cycles and 8-cycles (Chen et al. 2009 [14]).In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles adjacent to a triangle is acyclically 4-choosable, which covers these four results.     

平面图3色可染的一个充分条件

Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1.     

A 3-color Theorem on Plane Graphs without 5-circuits

In this paper, we prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O. V., Raspaud, A.： A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, Ser. B, 88, 17-27 （2003）], and provides a new upper bound to their conjecture.     

Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles

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(G). 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 it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245-260], and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (4) (2006) 281-300].     

Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable

It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable (Borodin et al., 2005) [13] and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable (Borodin et al., 2006) [11]. We give a common extension of these results by proving that every planar graph in which no triangles have common edges with k-cycles, where k∈{4,5,7} (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable.     

Bordeaux 3-color conjecture and 3-choosability

A graph G=(V,E) is list L-colorable if for a given list assignment L={L(v):v∈V}, there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is list L-colorable for every list assignment with |L(v)|?k for all v∈V, then G is said to be k-choosable.In this paper, we prove that (1) every planar graph either without 4- and 5-cycles, and without triangles at distance less than 4, or without 4-, 5- and 6-cycles, and without triangles at distance less than 3 is 3-choosable; (2) there exists a non-3-choosable planar graph without 4-cycles, 5-cycles, and intersecting triangles. These results have some consequences on the Bordeaux 3-color conjecture by Borodin and Raspaud [A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B 88 (2003) 17-27].     

A sufficient condition on 3-colorable plane graphs without 5- and 6-circuits

In 2003, Borodin and Raspaud proved that if G is a plane graph without 5-circuits and without triangles of distance less than four, then G is 3-colorable. In this paper, we prove that if G is a plane graph without 5- and 6-circuits and without triangles of distance less than 2, then G is 3-colorable.     

DP-4-colorability of planar graphs without intersecting 5-cycles

DP-coloring of graphs as a generalization of list coloring was introduced by Dvo?ák and Postle (2018). In this paper, we show that every planar graph without intersecting 5-cycles is DP-4-colorable, which improves the result of Hu and Wu (2017), who proved that every planar graph without intersecting 5-cycles is 4-choosable, and the results of Kim and Ozeki (2018).     

Acyclic 5-choosability of planar graphs without 4-cycles

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 without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-choosable.     

A note on the Three Color Problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles

Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. This conjecture is disproved by constructing a planar graph with no cycles of length four or five but intersecting triangles. Jin et al. proved that plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable [SIAM J. Discrete Math. 31 (3) (2017) 1836–1847]. In this paper, we point out a mistake of their proof and give an improved proof.     

On acyclic edge coloring of planar graphs without intersecting triangles

Let Δ denote the maximum degree of a graph. Fiam?ík first and then Alon et al. again conjectured that every graph is acyclically edge (Δ+2)-colorable. Even for planar graphs, this conjecture remains open. It is known that every triangle-free planar graph is acyclically edge (Δ+5)-colorable. This paper proves that every planar graph without intersecting triangles is acyclically edge (Δ+4)-colorable.     

Acyclic 6-choosability of planar graphs without adjacent short cycles

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).     

A non-3-choosable planar graph without cycles of length 4 and 5

Steinberg's question from 1975 whether every planar graph without 4- and 5-cycles is 3-colorable is still open. In this paper the analogous question for 3-choosability of such graphs is answered to the negative.     

A note on the acyclic 3-choosability of some planar graphs

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two adjacent vertices in G receive the same color and (ii) no bicolored cycles exist in G. A list assignment of G is a function L that assigns to each vertex v∈V(G) a list L(v) of available colors. Let G be a graph and L be a list assignment of G. The graph G is acyclically L-list colorable if there exists an acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is said to be acyclically k-choosable. Borodin et al. proved that every planar graph with girth at least 7 is acyclically 3-choosable (Borodin et al., submitted for publication [4]). More recently, Borodin and Ivanova showed that every planar graph without cycles of length 4 to 11 is acyclically 3-choosable (Borodin and Ivanova, submitted for publication [7]). In this note, we connect these two results by a sequence of intermediate sufficient conditions that involve the minimum distance between 3-cycles: we prove that every planar graph with neither cycles of lengths 4 to 7 (resp. to 8, to 9, to 10) nor triangles at distance less than 7 (resp. 5, 3, 2) is acyclically 3-choosable.