On Star 5-Colorings of Sparse Graphs

Abstract

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)\le 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.

arXiv comment28 pages, 18 figures