Packing chromatic vertex-critical graphs

MaRDI QIDQ5377230zbMATHFDO

Authors Sandi Klavžar, Douglas F. Rall

Publication date 23 May 2019

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)

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.

Recommendations

• Graphs that are critical for the packing chromatic number
• \(S\)-packing chromatic vertex-critical graphs
• Packing chromatic number of certain fan and wheel related graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

Cited in

(8)

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

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)