Albertson, Michael O.; Chappell, Glenn G.; Kierstead, H. A.; Kündgen, André; Ramamurthi, Radhika Coloring with no 2-colored \(P_4\)’s. (English) Zbl 1053.05045 Electron. J. Comb. 11, No. 1, Research paper R26, 13 p. (2004); printed version J. Comb. 11, No. 1 (2004). 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 G. Fertin, A. Raspaud and 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. Cited in 2 ReviewsCited in 76 Documents MSC: 05C15 Coloring of graphs and hypergraphs Keywords:coloring; star coloring; acyclic colorings Citations:Zbl 1042.68628 PDFBibTeX XMLCite \textit{M. O. Albertson} et al., Electron. J. Comb. 11, No. 1, Research paper R26, 13 p. (2004; Zbl 1053.05045) Full Text: EuDML EMIS