On colorings of squares of outerplanar graphs
Geir Agnarsson, Magnús M. Halldórsson · 2004
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 ∆ of G for all ∆ ∈ N. As a bonus, we obtain the optimal bound of the choosability (or the list-chromatic number) of G 2 when ∆ ≥ 7. In the case of chordal outerplanar graphs, we classify exactly which graphs have parameters exceeding the absolute minimum.