Geodesic
Graphs that are Critical for the Packing Chromatic Number
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

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/

[1] J. Balogh, A. Kostochka and X. Liu, Packing chromatic number of cubic graphs, Discrete Math. 341 (2018) 474–483. https://doi.org/10.1016/j.disc.2017.09.014

[2] J. Balogh, A. Kostochka and X. Liu, Packing chromatic number of subdivisions of cubic graphs, Graphs Combin. 35 (2019) 513–537. https://doi.org/10.1007/s00373-019-02016-3

[3] B. Brešar and J. Ferme, Packing coloring of Sierpiński-type graphs, Aequationes Math. 92 (2018) 1091–1118. https://doi.org/10.1007/s00010-018-0561-8

[4] B. Brešar and J. Ferme, An infinite family of subcubic graphs with unbounded packing chromatic number, Discrete Math. 341 (2018) 2337–2342. https://doi.org/10.1016/j.disc.2018.05.004

[5] B. Brešar, S. Klavžar, D.F. Rall and K. Wash, Packing chromatic number under local changes in a graph, Discrete Math. 340 (2017) 1110–1115. https://doi.org/10.1016/j.disc.2016.09.030

[6] B. Brešar, S. Klavžar, D.F. Rall and K. Wash, Packing chromatic number versus chromatic and clique number, Aequationes Math. 92 (2018) 497–513. https://doi.org/10.1007/s00010-017-0520-9

[7] J. Ekstein, P. Holub and O. Togni, The packing coloring of distance graphs D ( k, t ), Discrete Appl. Math. 167 (2014) 100–106. https://doi.org/10.1016/j.dam.2013.10.036

[8] J. Fiala and P.A. Golovach, Complexity of the packing coloring problem for trees, Discrete Appl. Math. 158 (2010) 771–778. https://doi.org/10.1016/j.dam.2008.09.001

[9] N. Gastineau, P. Holub and O. Togni, On the packing chromatic number of subcubic outerplanar graphs, Discrete Appl. Math. 255 (2019) 209–221. https://doi.org/10.1016/j.dam.2018.07.034

[10] W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, J.M. Harris and D.F. Rall, Broadcast chromatic numbers of graphs, Ars Combin. 86 (2008) 33–49.

[11] M. Kim, B. Lidický, T.Masařik and F. Pfender, Notes on complexity of packing coloring, Inform. Process. Lett. 137 (2018) 6–10. https://doi.org/10.1016/j.ipl.2018.04.012

[12] S. Klavžar and D.F. Rall, Packing chromatic vertex-critical graphs, Discrete Math. Theor. Comput. Sci. 21(3) (2019) #P8. https://doi.org/10.23638/DMTCS-21-3-8

[13] D. Korže and A. Vesel, ( d, n )- packing colorings of infinite lattices, Discrete Appl. Math. 237 (2018) 97–108. https://doi.org/10.1016/j.dam.2017.11.036

[14] D. Korže and A. Vesel, Packing coloring of generalized Sierpiński graphs, Discrete Math. Theor. Comput. Sci. 21 (2019) #P7. https://doi.org/10.23638/DMTCS-21-3-7

[15] B. Martin, F. Raimondi, T. Chen and J. Martin, The packing chromatic number of the infinite square lattice is between 13 and 15, Discrete Appl. Math. 225 (2017) 136–142. https://doi.org/10.1016/j.dam.2017.03.013

[16] D. Laïche and É. Sopena, Packing colouring of some classes of cubic graphs, Australas. J. Combin. 72 (2018) 376–404.

[17] D. Laïche, I. Bouchemakh and É. Sopena, Packing coloring of some undirected and oriented coronae graphs, Discuss. Math. Graph Theory 37 (2017) 665–690. https://doi.org/10.7151/dmgt.1963

[18] Z. Shao and A. Vesel, Modeling the packing coloring problem of graphs, Appl. Math. Model. 39 (2015) 3588–3595. https://doi.org/10.1016/j.apm.2014.11.060

[19] O. Togni, On packing colorings of distance graphs, Discrete Appl. Math. 167 (2014) 280–289. https://doi.org/10.1016/j.dam.2013.10.026

[20] P. Torres and M. Valencia-Pabon, The packing chromatic number of hypercubes, Discrete Appl. Math. 190–191 (2015) 127–140. https://doi.org/10.1016/j.dam.2015.04.006

[21] D.B. West, Introduction to Graph Theory (Prentice Hall, New York, 2001).