Acyclic coloring of graphs without bichromatic long path

作     者：Jianfeng HOU Shufei WU 

作者机构：Center for Discrete Mathematics F~tzhou University ~hlzhou 350003 China 

出 版 物：《Frontiers of Mathematics in China》 (中国高等学校学术文摘·数学（英文）)

年 卷 期：2015年第10卷第6期

页      面：1343-1354页

核心收录：

学科分类：07[理学] 070601[理学-气象学] 070104[理学-应用数学] 0706[理学-大气科学] 0701[理学-数学] 

基　　金：Acknowledgements The authors would like to thank the referees for providing some very helpful suggestions for revising this paper. This work was supported in part by the National Natural Science Foundation of China (Grant No. 11331003) 

主　　题：Coloring acyclic path entropy compression 

摘      要：Let G be a graph of maximum degree A. 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.