Packing coloring of Sierpiński-type graphs

Abstract

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$, $i\in \{1,\dots ,k\}$, where each $V_i$ 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 $S{T}_3^n$ is bounded from above by $31$. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs $S_G^n$ with respect to all connected graphs $G$ of order 4.

26 pages, 16 figures