RESEARCH ARTICLE

Acyclic coloring of graphs without bichromatic long path

  • Jianfeng HOU ,
  • Shufei WU
Expand
  • Center for Discrete Mathematics, Fuzhou University, Fuzhou 350003, China

Received date: 16 Apr 2014

Accepted date: 12 Aug 2015

Published date: 12 Oct 2015

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

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 O4/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.

Cite this article

Jianfeng HOU , Shufei WU . Acyclic coloring of graphs without bichromatic long path[J]. Frontiers of Mathematics in China, 2015 , 10(6) : 1343 -1354 . DOI: 10.1007/s11464-015-0497-4

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

Outlines

/