On Colorings of Squares of Outerplanar Graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 $Δ\in \nats$. As a bonus, we obtain the optimal bound of the choosability (or the list-chromatic number) of $G^2$ when $Δ\geq 7$. In the case of chordal outerplanar graphs, we classify exactly which graphs have parameters exceeding the absolute minimum.
24 pages, 17 figures

Keywords

Combinatorics, 05C15

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/130150

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0706.1526
 http://arxiv.org/abs/0706.1526

Collections

arXiv