Coloring with no 2-Colored P_4’s - Albertson, Michael O.; Chappell, Glenn G.; Kierstead, H. A.; Kündgen, André; Ramamurthi, Radhika (The Electronic Journal of Combinatorics, 2004)
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 Fertin, Raspaud, and Reed that graphs with tree-width t can be star colored with t+22 colors, and we show that this is best possible.