Acyclic 4-colorability of planar graphs without cycles of length 4 or 6

Every planar graph is known to be acyclically 5-colorable (O. V. Borodin, 1976), which bound is precise. Some sufficient conditions are also obtained for a planar graph to be acyclically 4-colorable. In particular, the acyclic 4-colorabilitywas 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 (M. Montassier, A. Raspaud, and W. Wang, 2006), and either without 4-, 6-, and 7-cycles or without 4-, 6-, and 8-cycles (M. Chen, A. Raspaud, and W. Wang, 2009). In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles is acyclically 4-colorable.     

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.     

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 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 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].     

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.     

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.     

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].     

平面图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.     

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).     

Acyclic improper choosability of graphs

We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically (3, 1)*-choosable (i.e. they are acyclically 3-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically (2, 5)*-choosable (i.e. they are acyclically 2-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability and acyclic improper choosability of planar graphs are equivalent notions.     

On 3-choosable planar graphs of girth at least 4

Let G be a plane graph of girth at least 4. Two cycles of G are intersecting if they have at least one vertex in common. In this paper, we show that if a plane graph G has neither intersecting 4-cycles nor a 5-cycle intersecting with any 4-cycle, then G is 3-choosable, which extends one of Thomassen’s results [C. Thomassen, 3-list-coloring planar graphs of girth 5, J. Combin. Theory Ser. B 64 (1995) 101-107].     

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).     

3-list-coloring planar graphs of girth 4

In Thomassen (1995) [4], Thomassen proved that planar graphs of girth at least 5 are 3-choosable. In Li (2009) [3], Li improved Thomassen’s result by proving that planar graphs of girth 4 with no 4-cycle sharing a vertex with another 4- or 5-cycle are 3-choosable. In this paper, we prove that planar graphs of girth 4 with no 4-cycle sharing an edge with another 4- or 5-cycle are 3-choosable. It is clear that our result strengthens Li’s result.     

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.     

List 2-facial 5-colorability of plane graphs with girth at least 12

A proper vertex coloring of a plane graph is 2-facial if any two different vertices joined by a facial walk of length 2 are colored differently, and it is 2-distance if every two vertices at distance 2 from each other are colored differently. Note that any 2-facial coloring of a subcubic graph is 2-distance.It is known that every plane graph with girth at least 14 has a 2-facial 5-coloring [M. Montassier, A. Raspaud, A note on 2-facial coloring of plane graphs. Inform. Process. Lett. 98 (6) (2006) 235–241], and that every planar subcubic graph with girth at least 13 has a list 2-distance 5-coloring [F. Havet, Choosability of square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353–3563].We strengthen these results by proving the list 2-facial 5-colorability of plane graphs with girth at least 12.     

Planar graphs without 3-, 7-, and 8-cycles are 3-choosable

A graph G is k-choosable if every vertex of G can be properly colored whenever every vertex has a list of at least k available colors. Grötzsch’s theorem [4] states that every planar triangle-free graph is 3-colorable. However, Voigt [M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325-328] gave an example of such a graph that is not 3-choosable, thus Grötzsch’s theorem does not generalize naturally to choosability. We prove that every planar triangle-free graph without 7- and 8-cycles is 3-choosable.     

无8-,9-和10-圈的平面图的3-可选择性

寻找平面图是3-或者4-可选择的充分条件是图的染色理论中一个重要研究课题,本文研究了围长至少是4的特殊平面图的选择数,通过权转移的方法证明了每个围长至少是4且不合8-圈,9-圈和10-圈的平面图是3-可选择的．