| Summary: | The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest
integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$,
$i\in [k]$, where vertices in $V_i$ are pairwise at distance at least $i+1$.
Packing chromatic vertex-critical graphs, $\chi_{\rho}$-critical for short, are
introduced as the graphs $G$ for which $\chi_{\rho}(G-x) < \chi_{\rho}(G)$
holds for every vertex $x$ of $G$. If $\chi_{\rho}(G) = k$, then $G$ is
$k$-$\chi_{\rho}$-critical. It is shown that if $G$ is $\chi_{\rho}$-critical,
then the set $\{\chi_{\rho}(G) - \chi_{\rho}(G-x):\ x\in V(G)\}$ can be almost
arbitrary. The $3$-$\chi_{\rho}$-critical graphs are characterized, and
$4$-$\chi_{\rho}$-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 $k\ge 2$ there exists a
$k$-$\chi_{\rho}$-critical tree and that a $k$-$\chi_{\rho}$-critical
caterpillar exists if and only if $k\le 7$. Cartesian products are also
considered and in particular it is proved that if $G$ and $H$ are
vertex-transitive graphs and ${\rm diam(G)} + {\rm diam}(H) \le
\chi_{\rho}(G)$, then $G\,\square\, H$ is $\chi_{\rho}$-critical.
|
|---|