Packing coloring of generalized Sierpinski graphs

zbMATH Open1411.05092arXiv1809.09908MaRDI QIDQ5377229FDOQ5377229

Authors: Danilo Korže, Aleksander Vesel 

Publication date: 23 May 2019

Abstract: The packing chromatic number $ch{i}_{ho}(G)$ of a graph $G$ is the smallest integer $c$ such that the vertex set $V(G)$ can be partitioned into sets $X_1,\mathrm{...},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_G^n$ 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 $S{T}_4^n$ is bounded from above by 20.

Full work available at URL: https://arxiv.org/abs/1809.09908

Recommendations

• Packing coloring of Sierpiński-type graphs
• Packing chromatic number of base-3 Sierpiński graphs
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs
• A survey on packing colorings
• The \(S\)-packing chromatic number of a graph

zbMATH Keywords

coloringpacking coloringgeneralized Sierpiński graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (18)

• Packing chromatic number of base-3 Sierpiński graphs
• On the packing coloring of undirected and oriented generalized theta graphs
• A study on packing coloring of fan and jump graph families
• The packing coloring problem for lobsters and partner limited graphs
• \(S\)-packing colorings of cubic graphs
• A survey on packing colorings
• The Sierpiński domination number
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
• Graphs that are critical for the packing chromatic number
• Independence number and packing coloring of generalized Mycielski graphs
• Packing coloring of Sierpiński-type graphs
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs
• Gröbner bases techniques for an \(S\)-packing \(k\)-coloring of a graph
• \(S\)-packing chromatic vertex-critical graphs
• The \(S\)-packing chromatic number of a graph
• Packing coloring of some undirected and oriented coronae graphs
• Packing chromatic numbers of finite super subdivisions of graphs
• The linear \(t\)-colorings of Sierpiński-like graphs

This page was built for publication: Packing coloring of generalized Sierpinski graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377229)