Star coloring of sparse graphs
Yuehua Bu, Daniel W. Cranston, Mickaël Montassier, André Raspaud, Weifan Wang · 2009
A proper coloring of the vertices of a graph is called a star coloring if the union of every two color classes induce a star forest. The star chromatic number χs(G) is the smallest number of colors required to obtain a star coloring of G. In this paper, we study the relationship between the star chromatic number χs(G) and the maximum average degree Mad(G) of a graph G. We prove that: 1. If G is a graph with Mad(G) < 26, then χs(G) ≤ 4.