×

Coloring the square of an outerplanar graph. (English) Zbl 1135.05022

Summary: Let \(G\) be an outerplanar graph with maximum degree \(\Delta(G)\geq 3\). We prove that the chromatic number \(\chi(G^2)\) of the square of \(G\) is at most \(\Delta(G)+2\). This confirms a conjecture of G. Wegner [Graphs with given diameter and a coloring problem, preprint, University Dortmund (1977)] for outerplanar graphs. The upper bound can be further reduced to the optimal value \(\Delta(G)+1\) when \(\Delta(G)\geq 7\).

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI