Abstract
Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ≠= 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.
Original language | English |
---|---|
Pages (from-to) | 619-636 |
Number of pages | 18 |
Journal | Discussiones Mathematicae - Graph Theory |
Volume | 30 |
Issue number | 4 |
DOIs | |
Publication status | Published - 2010 |
Other keywords
- Chromatic number
- Outerplanar
- Power of a graph
- Weak dual