Thumbnail - No thumbnail

On the packing chromatic number of subcubic outerplanar graphs

Gastineau, Nicolas; Holub, Přemysl; Togni, Olivier (2019), On the packing chromatic number of subcubic outerplanar graphs, Discrete Applied Mathematics, 255, p. 209-221. 10.1016/j.dam.2018.07.034

Type
Article accepté pour publication ou publié
External document link
https://arxiv.org/abs/1703.05023v3
Date
2019
Journal name
Discrete Applied Mathematics
Volume
255
Publisher
Elsevier
Pages
209-221
Publication identifier
Metadata
Show full item record
Author(s)
Gastineau, Nicolas
Holub, Přemysl
Togni, Olivier cc
Abstract (EN)
Although it has recently been proved that the packing chromatic number is unbounded on the class of subcubic graphs, there exist subclasses in which the packing chromatic number is finite (and small). These subclasses include subcubic trees, base-3 Sierpiński graphs and hexagonal lattices. In this paper we are interested in the packing chromatic number of subcubic outerplanar graphs. We provide asymptotic bounds depending on structural properties of the outerplanar graphs and determine sharper bounds for some classes of subcubic outerplanar graphs.
Subjects / Keywords
Packing colouring; Packing chromatic number; Outerplanar graphs; Subcubic graphs