On Star 5-Colorings of Sparse Graphs

Ilkyoo Choi, Boram Park

Published 2019-03-25Version 1

Given a graph $G$, a star $k$-coloring of $G$ is a proper vertex $k$-coloring of $G$ such that the vertices on a path of length three receive at least three colors. The star chromatic number, denoted $\chi_s(G)$, of a graph $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 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)<{8\over 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$. For a graph $G$, let $\Delta(G)$ denote the maximum degree of $G$. In this paper, we show that for a graph $G$, if mad$(G)\le \frac{8}{3}$ and $\Delta(G)\not\in\{4,5,6\}$ then $\chi_s(G)\le 5$.