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.05023v3Date
2019Journal name
Discrete Applied MathematicsVolume
255Publisher
Elsevier
Pages
209-221
Publication identifier
Metadata
Show full item recordAbstract (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 graphsRelated items
Showing items related by title and author.
-
Gastineau, Nicolas; Togni, Olivier (2019) Article accepté pour publication ou publié
-
Darties, Benoit; Gastineau, Nicolas; Togni, Olivier (2018) Article accepté pour publication ou publié
-
Moinet, Axel; Darties, Benoit; Gastineau, Nicolas; Baril, Jean-Luc; Togni, Olivier (2017) Communication / Conférence
-
Bazgan, Cristina; Bentz, Cédric; Picouleau, Christophe; Ries, Bernard (2015) Article accepté pour publication ou publié
-
Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié