Acyclic coloring of graphs without bichromatic long path

摘要

Let G be a graph of maximum degree Delta. 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(Delta(4/3)) colors and a proper coloring with O(Delta((k-1)/(k-2))) colors such that no path with k vertices is bichromatic for a fixed integer k a parts per thousand yen 5. In this paper, we combine above two colorings and show that if k a parts per thousand yen 5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Delta((k-1)/(k-2))) colors such that no path with k vertices is bichromatic.