Coloring with no 2-colored P4's

Michael O. Albertson, Glenn G. Chappell, Henry Kierstead, André Kündgen, Radhika Ramamurthi

Research output: Contribution to journalArticlepeer-review

115 Scopus citations


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 (2k2 - 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 (2t+2) colors, and we show that this is best possible.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Issue number1 R
StatePublished - Mar 31 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Coloring with no 2-colored P4's'. Together they form a unique fingerprint.

Cite this