Coloring with no $2$-Colored $P_4$'s

Authors:
  • MAMichael O. Albertson
    Michael O. Albertson
  • GCGlenn G. Chappell
    Glenn G. Chappell
  • HKH. A. Kierstead
    H. A. Kierstead
  • AKAndré Kündgen
    André Kündgen
  • RRRadhika Ramamurthi
    Radhika Ramamurthi

Abstract
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+2\choose2}$ colors, and we show that this is best possible.