Acyclic coloring of graphs without bichromatic long path

doi:10.1007/s11464-015-0497-4

Front. Math. China

2015, Vol. 10

Issue (6) : 1343-1354 https://doi.org/10.1007/s11464-015-0497-4

RESEARCH ARTICLE

Acyclic coloring of graphs without bichromatic long path

Jianfeng HOU,Shufei WU(

)

Center for Discrete Mathematics, Fuzhou University, Fuzhou 350003, China

Download: PDF(149 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Shufei WU

Issue Date: 12 October 2015

Cite this article:

Jianfeng HOU,Shufei WU. Acyclic coloring of graphs without bichromatic long path[J]. Front. Math. China, 2015, 10(6): 1343-1354.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-015-0497-4
https://academic.hep.com.cn/fmc/EN/Y2015/V10/I6/1343

1	Alon N, Mcdiarmid C, Reed B. Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277−288 https://doi.org/10.1002/rsa.3240020303
2	Alon N, Mohar B, Sanders D P. On acyclic colorings of graphs on surfaces. Israel J Math, 1996, 94(1): 273−283 https://doi.org/10.1007/BF02762708
3	Borodin O V. On acyclic colorings of planar graphs. Discrete Math, 1979, 25(3): 211−236 https://doi.org/10.1016/0012-365X(79)90077-3
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 https://doi.org/10.1002/jgt.10035
5	Borodin O V, Kostochka A V, Raspaud A, Sopena É. Acyclic colouring of 1-planar graphs. Discrete Appl Math, 2001, 114(1): 29−41 https://doi.org/10.1016/S0166-218X(00)00359-0
6	Chen M, Raspaud A. A sufficient condition for planar graphs to be acyclically 5-choosable. J Graph Theory, 2012, 70(2): 135−151 https://doi.org/10.1002/jgt.20604
7	Chen M, Raspaud A. Planar graphs without 4- and 5-cycles are acyclically 4-choosable. Discrete Appl Math, 2013, 161: 921−931 https://doi.org/10.1016/j.dam.2012.11.006
8	Chen M, Raspaud A, Roussel N, Zhu X. Acyclic 4-choosability of planar graphs. Discrete Math, 2011, 311(1): 92−101 https://doi.org/10.1016/j.disc.2010.10.003
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 https://doi.org/10.1137/0607026
10	Coleman T F, Moré J J. Estimation of sparse Hessian matrices and graph coloring problems. Math Program, 1984, 28(3): 243−270 https://doi.org/10.1007/BF02612334
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 https://doi.org/10.1016/j.ejc.2013.02.007
13	Fertin G, Raspaud A, Reed B. Star coloring of graphs. J Graph Theory, 2004, 47(3): 163−182 https://doi.org/10.1002/jgt.20029
14	Flajolet P, Sedgewick R. Analytic Combinatorics. London: Cambridge University Press, 2009 https://doi.org/10.1017/CBO9780511801655
15	Grünbaum B. Acyclic colorings of planar graphs. Israel J Math, 1973, 14(4): 390−408 https://doi.org/10.1007/BF02764716
16	Kostochka A V, Mel’nikov L. Note to the paper of Grünbaum on acyclic colorings. Discrete Math, 1976, 14(4): 403−406 https://doi.org/10.1016/0012-365X(76)90075-3
17	Kostochka A V, Sopena É, Zhu X. Acyclic and oriented chromatic numbers of graphs. J Graph Theory, 1997, 24(4): 331−340 https://doi.org/10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO;2-P
18	Montassier M, Raspaud A, Wang W. Acyclic 5-choosability of planar graphs without small cycles. J Graph Theory, 2007, 54(3): 245−260 https://doi.org/10.1002/jgt.20206
19	Moser R A, Tardos G. A constructive proof of the general Lovász Local Lemma. J ACM, 2010, 57(2): 11 https://doi.org/10.1145/1667053.1667060

[1]	Ziqiu LIU, Yunfeng ZHAO, Yuqin ZHANG. Perfect 3-colorings on 6-regular graphs of order 9[J]. Front. Math. China, 2019, 14(3): 605-618.
[2]	Hongjie SONG, Changqing XU. Neighbor sum distinguishing total chromatic number of K₄-minor free graph[J]. Front. Math. China, 2017, 12(4): 937-947.
[3]	Yingbin MA, Lily CHEN, Hengzhe LI. Graphs with small total rainbow connection number[J]. Front. Math. China, 2017, 12(4): 921-936.
[4]	Xi GENG, Zhongmin QIAN. Finite dimensional characteristic functions of Brownian rough path[J]. Front. Math. China, 2017, 12(4): 859-877.
[5]	Haiyan ZHU. Constructing cotorsion pairs over generalized path algebras[J]. Front. Math. China, 2016, 11(4): 1079-1096.
[6]	Junjie YUE,Liping ZHANG,Mei LU. Largest adjacency, signless Laplacian, and Laplacian H-eigenvalues of loose paths[J]. Front. Math. China, 2016, 11(3): 623-645.
[7]	Shaoqin ZHANG. Shift Harnack inequality and integration by parts formula for semilinear stochastic partial differential equations[J]. Front. Math. China, 2016, 11(2): 461-496.
[8]	Shanghua ZHENG,LI GUO. Relative locations of subwords in free operated semigroups and Motzkin words[J]. Front. Math. China, 2015, 10(5): 1243-1261.
[9]	Weisheng ZHAO,Heping ZHANG. Bondage number of strong product of two paths[J]. Front. Math. China, 2015, 10(2): 435-460.
[10]	Miao WANG,Jiang-Lun WU. Necessary and sufficient conditions for path-independence of Girsanov transformation for infinite-dimensional stochastic evolution equations[J]. Front. Math. China, 2014, 9(3): 601-622.
[11]	Benchong LI, Jianhua GUO. Decomposition of two classes of structural model[J]. Front Math Chin, 2013, 8(6): 1323-1349.
[12]	Wanlu DENG, Zhi GENG, Peng LUO. Identifiability of intermediate variables on causal paths[J]. Front Math Chin, 2013, 8(3): 517-539.
[13]	Changzhang WANG, You ZHOU, Zhi GENG. Discovering causes and effects of a given node in Bayesian networks[J]. Front Math Chin, 2013, 8(3): 643-663.
[14]	Xin ZHANG, Jianliang WU, Guizhen LIU. List edge and list total coloring of 1-planar graphs[J]. Front Math Chin, 2012, 7(5): 1005-1018.
[15]	Yun XUE, Yimin XIAO. Fractal and smoothness properties of space-time Gaussian models[J]. Front Math Chin, 2011, 6(6): 1217-1248.

Viewed

Full text

Abstract

Cited

Shared

Discussed