On the packing coloring of base-3 Sierpiński and $H$ graphs

Abstract

For a nondecreasing sequence of integers $S=(s_1,s_2,\dots )$ an $S$-packing $k$-coloring of a graph $G$ is a mapping from $V(G)$ to $\{1,2,\dots ,k\}$ such that vertices with color $i$ have pairwise distance greater than $s_i$. By setting $s_i=d+\lfloor \frac{i-1}{n}\rfloor$ we obtain a $(d,n)$-packing coloring of a graph $G$. The smallest integer $k$ for which there exists a $(d,n)$-packing coloring of $G$ is called the $(d,n)$-packing chromatic number of $G$. In the special case when $d$ and $n$ are both equal to one we speak of the packing chromatic number of $G$. We determine the packing chromatic number of the base-3 Sierpiński graphs $S_k$ and provide new results on $(d,n)$-packing chromatic colorings, $d\le 2$, for this class of graphs. By using a dynamic algorithm, we establish the packing chromatic number for $H$-graphs $H(r)$.