Packing chromatic vertex-critical graphs

zbMATH Open1411.05091arXiv1810.03904MaRDI QIDQ5377230FDOQ5377230

Douglas F. Rall, Sandi Klavžar

Publication date: 23 May 2019

Abstract: The packing chromatic number $ch{i}_{ho}(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$, $iin[k]$, where vertices in $V_i$ are pairwise at distance at least $i+1$. Packing chromatic vertex-critical graphs, $ch{i}_{ho}$-critical for short, are introduced as the graphs $G$ for which $ch{i}_{ho}(G-x)<ch{i}_{ho}(G)$ holds for every vertex $x$ of $G$. If $ch{i}_{ho}(G)=k$, then $G$ is $k$-$ch{i}_{ho}$-critical. It is shown that if $G$ is $ch{i}_{ho}$-critical, then the set $ch{i}_{ho}(G)-ch{i}_{ho}(G-x):xinV(G)$ can be almost arbitrary. The $3$-$ch{i}_{ho}$-critical graphs are characterized, and $4$-$ch{i}_{ho}$-critical graphs are characterized in the case when they contain a cycle of length at least $5$ which is not congruent to $0$ modulo $4$. It is shown that for every integer $kge2$ there exists a $k$-$ch{i}_{ho}$-critical tree and that a $k$-$ch{i}_{ho}$-critical caterpillar exists if and only if $kle7$. Cartesian products are also considered and in particular it is proved that if $G$ and $H$ are vertex-transitive graphs and $mdiam(G)+mdiam(H)lech{i}_{ho}(G)$, then $G,square,H$ is $ch{i}_{ho}$-critical.

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

zbMATH Keywords

treeCartesian product of graphspacking chromatic numbervertex-transitive graphcaterpillarpacking chromatic vertex-critical graph

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Cited In (8)

• A survey on packing colorings
• Packing chromatic number of distance graphs
• Graphs that are critical for the packing chromatic number
• A characterization of 4-\(\chi_S\)-vertex-critical graphs for packing sequences with \(s_1 = 1\) and \(s_2 \geq 3\)
• Packing chromatic number under local changes in a graph
• \(S\)-packing chromatic vertex-critical graphs
• Packing $k$-Matchings and $k$-Critical Graphs
• Packing chromatic numbers of finite super subdivisions of graphs

This page was built for publication: Packing chromatic vertex-critical graphs

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