Packing chromatic vertex-critical graphs

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 f...

Full description

Bibliographic Details
Main Authors: Sandi Klavžar, Douglas F. Rall
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2019-02-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
Online Access:https://dmtcs.episciences.org/4878/pdf
_version_ 1797270027246764032
author Sandi Klavžar
Douglas F. Rall
author_facet Sandi Klavžar
Douglas F. Rall
author_sort Sandi Klavžar
collection DOAJ
description 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.
first_indexed 2024-04-25T01:57:44Z
format Article
id doaj.art-b28f75f16b484e539bfb1466dc7463e2
institution Directory Open Access Journal
issn 1365-8050
language English
last_indexed 2024-04-25T01:57:44Z
publishDate 2019-02-01
publisher Discrete Mathematics & Theoretical Computer Science
record_format Article
series Discrete Mathematics & Theoretical Computer Science
spelling doaj.art-b28f75f16b484e539bfb1466dc7463e22024-03-07T15:39:17ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-02-01Vol. 21 no. 3Graph Theory10.23638/DMTCS-21-3-84878Packing chromatic vertex-critical graphsSandi KlavžarDouglas F. RallThe 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.https://dmtcs.episciences.org/4878/pdfmathematics - combinatorics
spellingShingle Sandi Klavžar
Douglas F. Rall
Packing chromatic vertex-critical graphs
Discrete Mathematics & Theoretical Computer Science
mathematics - combinatorics
title Packing chromatic vertex-critical graphs
title_full Packing chromatic vertex-critical graphs
title_fullStr Packing chromatic vertex-critical graphs
title_full_unstemmed Packing chromatic vertex-critical graphs
title_short Packing chromatic vertex-critical graphs
title_sort packing chromatic vertex critical graphs
topic mathematics - combinatorics
url https://dmtcs.episciences.org/4878/pdf
work_keys_str_mv AT sandiklavzar packingchromaticvertexcriticalgraphs
AT douglasfrall packingchromaticvertexcriticalgraphs