Injective chromatic number of outerplanar graphs

Abstract

An injective coloring of a graph is a vertex coloring where two vertices with common neighbor receive distinct colors. The minimum integer $k$ that $G$ has a $k-$injective coloring is called injective chromatic number of $G$ and denoted by ${\chi }_i(G)$. In this paper, the injective chromatic number of outerplanar graphs with maximum degree $\Delta$ and girth $g$ is studied. It is shown that for every outerplanar graph, ${\chi }_i(G)\le \Delta +2$, and this bound is tight. Then, it is proved that for outerplanar graphs with $\Delta =3$, ${\chi }_i(G)\le \Delta +1$ and the bound is tight for outerplanar graphs of girth three and $4$. Finally, it is proved that, the injective chromatic number of $2-$connected outerplanar graphs with $\Delta =3$, $g\ge 6$ and $\Delta \ge 4$, $g\ge 4$ is equal to $\Delta$.

13 pages, 6 figures