Star-coloring planar graphs with high girth

-
Dan Cranston, Rutgers University and Bell Labs
Fine Hall 314

A star-coloring is a proper vertex-coloring such that the graph induced by the union of any 2 color classes is a star-forest. Equivalently, it is a proper vertex-coloring with no 2-colored $P_4$. Star-coloring has been studied extensively, even for planar graphs. However, little is known about improved upper bounds for planar graphs with large girth. We prove that a planar graph with girth at least 13 has star-chromatic number at most 4. We use the discharging method to prove a structural lemma about planar graphs with girth at least 13. It is then straightforward to construct the 4-star-coloring using this lemma. This is joint work with Craig Timmons and Andre Kundgen of Cal State, San Marcos.