Danilo Korze ; Aleksander Vesel - Packing coloring of generalized Sierpinski graphs

dmtcs:4862 - Discrete Mathematics & Theoretical Computer Science, February 8, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-7
Packing coloring of generalized Sierpinski graphsArticle

Authors: Danilo Korze ; Aleksander Vesel

    The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $c$ such that the vertex set $V(G)$ can be partitioned into sets $X_1, . . . , X_c$, with the condition that vertices in $X_i$ have pairwise distance greater than $i$. In this paper, we consider the packing chromatic number of several families of Sierpinski-type graphs. We establish the packing chromatic numbers of generalized Sierpinski graphs $S^n_G$ where $G$ is a path or a cycle (with exception of a cycle of length five) as well as a connected graph of order four. Furthermore, we prove that the packing chromatic number in the family of Sierpinski-triangle graphs $ST_4^n$ is bounded from above by 20.


    Volume: Vol. 21 no. 3
    Section: Graph Theory
    Published on: February 8, 2019
    Accepted on: January 24, 2019
    Submitted on: October 1, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 731 times.
    This article's PDF has been downloaded 382 times.