$2$-distance $(\Delta +1)$-coloring of sparse graphs using the potential method

Abstract

A $2$-distance $k$-coloring of a graph is a proper $k$-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance ($\Delta +1$)-coloring for graphs with maximum average degree less than $\frac{18}{7}$ and maximum degree $\Delta \ge 7$. As a corollary, every planar graph with girth at least $9$ and $\Delta \ge 7$ admits a $2$-distance $(\Delta +1)$-coloring. The proof uses the potential method to reduce new configurations compared to classic approaches on $2$-distance coloring.

26 pages, 17 figures