Acyclic coloring of graphs without bichromatic long path

Abstract

Let G be a graph of maximum degree Δ. A proper vertex coloring of G is acyclic if there is no bichromatic cycle. It was proved by Alon et al. [Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277−288] that G admits an acyclic coloring with O(Δ^4/3) colors and a proper coloring with O(Δ^{(k−1)/(k−2)}) colors such that no path with k vertices is bichromatic for a fixed integer k≥5. In this paper, we combine above two colorings and show that if k≥5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Δ^{(k−1)/(k−2)}) colors such that no path with k vertices is bichromatic.

Keywords

Coloring / acyclic / path / entropy compression

References

[1] Alon N, Mcdiarmid C, Reed B. Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277−288

[2] Alon N, Mohar B, Sanders D P. On acyclic colorings of graphs on surfaces. Israel J Math, 1996, 94(1): 273−283

[3] Borodin O V. On acyclic colorings of planar graphs. Discrete Math, 1979, 25(3): 211−236

[4] Borodin O V, Flaass F D, Kostochka A V, Raspaud A, Sopena É. Acyclic list 7-coloring of planar graphs. J Graph Theory, 2002, 40(2): 83−90

[5] Borodin O V, Kostochka A V, Raspaud A, Sopena É. Acyclic colouring of 1-planar graphs. Discrete Appl Math, 2001, 114(1): 29−41

[6] Chen M, Raspaud A. A sufficient condition for planar graphs to be acyclically 5-choosable. J Graph Theory, 2012, 70(2): 135−151

[7] Chen M, Raspaud A. Planar graphs without 4- and 5-cycles are acyclically 4-choosable. Discrete Appl Math, 2013, 161: 921−931

[8] Chen M, Raspaud A, Roussel N, Zhu X. Acyclic 4-choosability of planar graphs. Discrete Math, 2011, 311(1): 92−101

[9] Coleman T F, Cai J. The acyclic coloring problem and estimation of spare Hessian matrices. SIAM J Algebraic Discrete Methods, 1986, 7(2): 221−235

[10] Coleman T F, Moré J J. Estimation of sparse Hessian matrices and graph coloring problems. Math Program, 1984, 28(3): 243−270

[11] Drmota M. Combinatorics and asymptotics on trees. Cubo, 2004, 6(2): 105−136

[12] Esperet L, Parreau A. Acyclic edge-coloring using entropy compression. European J Combin, 2013, 34(6): 1019−1027

[13] Fertin G, Raspaud A, Reed B. Star coloring of graphs. J Graph Theory, 2004, 47(3): 163−182

[14] Flajolet P, Sedgewick R. Analytic Combinatorics. London: Cambridge University Press, 2009

[15] Grünbaum B. Acyclic colorings of planar graphs. Israel J Math, 1973, 14(4): 390−408

[16] Kostochka A V, Mel’nikov L. Note to the paper of Grünbaum on acyclic colorings. Discrete Math, 1976, 14(4): 403−406

[17] Kostochka A V, Sopena É, Zhu X. Acyclic and oriented chromatic numbers of graphs. J Graph Theory, 1997, 24(4): 331−340

[18] Montassier M, Raspaud A, Wang W. Acyclic 5-choosability of planar graphs without small cycles. J Graph Theory, 2007, 54(3): 245−260

[19] Moser R A, Tardos G. A constructive proof of the general Lovász Local Lemma. J ACM, 2010, 57(2): 11

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg