×

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.

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1042.68628
PDFBibTeX XMLCite
Full Text: EuDML EMIS