On Colorings of Squares of Outerplanar Graphs

Abstract

We study vertex colorings of the square $G^2$ of an outerplanar graph $G$. We find the optimal bound of the inductiveness, chromatic number and the clique number of $G^2$ as a function of the maximum degree $\Delta$ of $G$ for all $Δ\in \nats$. As a bonus, we obtain the optimal bound of the choosability (or the list-chromatic number) of $G^2$ when $\Delta \ge 7$. In the case of chordal outerplanar graphs, we classify exactly which graphs have parameters exceeding the absolute minimum.

24 pages, 17 figures