A \textit{ star $k$-coloring} of a graph $G$ is a proper (vertex) $k$-coloring of $G$ such that the vertices on a path of length three receive at least three colors. Given a graph $G$, its \textit{ star chromatic number}, denoted $\chi_s(G)$, is the minimum integer $k$ for which $G$ admits a star $k$-coloring. Studying star coloring of sparse graphs is an active area of research, especially in terms of the maximum average degree of a graph; the \textit{ maximum average degree}, denoted $mad(G)$, of a graph $G$ is $\max\left\{ \frac{ 2|E(H)|}{ |V(H)|}:{ H \subset G}\right\}$. It is known that for a graph $G$, if $mad(G)<\frac{ 8}{ 3}$, then $\chi_s(G)\leq 6$, and if $mad(G)< \frac{ 18}{ 7}$ and its girth is at least 6, then $\chi_s(G)\le 5$. We improve both results by showing that for a graph $G$, if $mad(G)\le \frac{ 8}{ 3}$, then $\chi_s(G)\le 5$. As an immediate corollary, we obtain that a planar graph with girth at least 8 has a star 5-coloring, improving the best known girth condition for a planar graph to have a star 5-coloring.
Categories: math.CO