摘要
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.
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.
基金
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）.
