Coloring the Square of Outerplanar Graphs
Nianfeng Lin · 2004
The square of a graph G, denoted by G^2, is a graph with the same vertex set such that two vertices are adjacent in G^2 iff their distance is at most 2 in G. In this article we determine the chromatic number of the square of cycles. For outerplanar graphs we get the following main result: Let G be a connected simple outerplanar graph with maximum degree △(G), G≠C5. Then X(G^2)≤△(G)+2.