Graphs that are Critical for the Packing Chromatic Number

Brešar, Boštjan; Ferme, Jasmina

Geodesic

Parcourir par

Graphs that are Critical for the Packing Chromatic Number

Brešar, Boštjan ; Ferme, Jasmina

Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 569-589

Voir la notice de l'article provenant de la source Library of Science

Résumé

Given a graph G, a coloring c : V (G) → 1, …, k such that c(u) = c(v) = i implies that vertices u and v are at distance greater than i, is called a packing coloring of G. The minimum number of colors in a packing coloring of G is called the packing chromatic number of G, and is denoted by χ_ρ(G). In this paper, we propose the study of χ_ρ-critical graphs, which are the graphs G such that for any proper subgraph H of G, χ_ρ(H) lt; χ_ρ(G). We characterize χ_ρ-critical graphs with diameter 2, and χ_ρ-critical block graphs with diameter 3. Furthermore, we characterize χ_ρ-critical graphs with small packing chromatic number, and we also consider χ_ρ-critical trees. In addition, we prove that for any graph G and every edge e ∈ E(G), we have (χ_ρ(G)+1)/2 ≤ χ_ρ(G−e) ≤ χ_ρ(G), and provide a corresponding realization result, which shows that χ_ρ(G − e) can achieve any of the integers between these bounds.

Keywords: packing coloring, critical graph, diameter, block graph, tree

@article{DMGT_2022_42_2_a13,
     author = {Bre\v{s}ar, Bo\v{s}tjan and Ferme, Jasmina},
     title = {Graphs that are {Critical} for the {Packing} {Chromatic} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {569--589},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a13/}
}

TY  - JOUR
AU  - Brešar, Boštjan
AU  - Ferme, Jasmina
TI  - Graphs that are Critical for the Packing Chromatic Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 569
EP  - 589
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a13/
LA  - en
ID  - DMGT_2022_42_2_a13
ER  -

%0 Journal Article
%A Brešar, Boštjan
%A Ferme, Jasmina
%T Graphs that are Critical for the Packing Chromatic Number
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 569-589
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a13/
%G en
%F DMGT_2022_42_2_a13

Brešar, Boštjan; Ferme, Jasmina. Graphs that are Critical for the Packing Chromatic Number. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 569-589. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a13/