2017/03/15 by Nicolas Gastineau, Gastineau, Nicolas, Přemysl Holub +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1703.05023
openalex publication_date 2017/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Although it has recently been proved that the packing chromatic number is unbounded on the class of subcubic graphs, there exists 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.