Packing coloring of generalized Sierpinski graphs

MaRDI QIDQ5377229zbMATH OpenFDO

Authors Danilo Korže, Aleksander Vesel

Publication date 23 May 2019

Full work available at URL https://arxiv.org/abs/1809.09908, https://dmtcs.episciences.org/5178/pdf

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)

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.

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

Cited in

(18)

• The linear \(t\)-colorings of Sierpiński-like graphs
• Packing chromatic number of base-3 Sierpiński graphs
• On the packing coloring of undirected and oriented generalized theta graphs
• \(S\)-packing colorings of cubic graphs
• The packing coloring problem for lobsters and partner limited graphs
• A study on packing coloring of fan and jump graph families
• A survey on packing colorings
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
• Graphs that are critical for the packing chromatic number
• The Sierpiński domination 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

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)