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.

Key words： 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