Injective colorings of sparse graphs

Abstract

Let $mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let ${\chi }_i(G)$ denote the injective chromatic number of $G$. We prove that if $mad(G)\le 5/2$, then ${\chi }_i(G)\le \Delta (G)+1$; and if $mad(G)<42/19$, then ${\chi }_i(G)=\Delta (G)$. Suppose that $G$ is a planar graph with girth $g(G)$ and $\Delta (G)\ge 4$. We prove that if $g(G)\ge 9$, then ${\chi }_i(G)\le \Delta (G)+1$; similarly, if $g(G)\ge 13$, then ${\chi }_i(G)=\Delta (G)$.

10 pages