Coloring with no 2-colored \(P_4\)'s (Q1883636)

Summary: A proper coloring of the vertices of a graph is called a star coloring if every two color classes induce a star forest. Star colorings are a strengthening of acyclic colorings, i.e., proper colorings in which every two color classes induce a forest. We show that every acyclic \(k\)-coloring can be refined to a star coloring with at most \((2k^2- k)\) colors. Similarly, we prove that planar graphs have star colorings with at most 20 colors and we exhibit a planar graph which requires 10 colors. We prove several other structural and topological results for star colorings, such as: cubic graphs are 7-colorable, and planar graphs of girth at least 7 are 9-colorable. We provide a short proof of the result of \textit{G. Fertin}, \textit{A. Raspaud} and \textit{B. Reed} [Lect. Notes Comput. Sci. 2204, 140--153 (2001; Zbl 1042.68628)] that graphs with tree-width \(t\) can be star colored with \({t+2\choose 2}\) colors, and we show that this is best possible.