Acyclic coloring of graphs without bichromatic long path

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.