2017/11/10 by Boštjan Brešar, Brešar, Boštjan, Jasmina Ferme +1 · 2 citations
Computer Science · Mathematics · #05C12 #05C15 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1711.03856
openalex publication_date 2017/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets Vi, i∈ \1,…,k\, where each Vi is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpiński-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpiński graphs with base 3, we prove that it is unbounded in the families of Sierpiński graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpiński triangle graphs STn3 is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs SnG with respect to all connected graphs G of order 4.