Article in volume
Authors:
Title:
Graphs that are critical for the packing chromatic number
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 569-589
Received: 2019-04-23 , Revised: 2019-12-16 , Accepted: 2019-12-16 , Available online: 2020-01-30 , https://doi.org/10.7151/dmgt.2298
Abstract:
Given a graph $G$, a coloring $c:V(G)\longrightarrow \{1,\ldots,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 $\chi_{\rho}(G)$. In this paper, we propose the study of $\chi_{\rho}$-critical
graphs, which are the graphs $G$ such that for any proper subgraph $H$ of $G$,
$\chi_{\rho}(H)<\chi_{\rho}(G)$. We characterize $\chi_{\rho}$-critical graphs with diameter 2, and
$\chi_{\rho}$-critical block graphs with diameter 3. Furthermore, we characterize
$\chi_{\rho}$-critical graphs with small packing chromatic number, and we also consider
$\chi_{\rho}$-critical trees. In addition, we prove that for any graph $G$ and every
edge $e\in E(G)$, we have $(\chi_{\rho}(G)+1)/2\le \chi_{\rho}(G-e)\le \chi_{\rho}(G)$, and provide
a corresponding realization result, which shows that $\chi_{\rho}(G-e)$ can achieve
any of the integers between these bounds.
Keywords:
packing coloring, critical graph, diameter, block graph, tree
References:
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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.
- 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 - 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 - 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 - 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 - 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 - D. Laïche and É. Sopena, Packing colouring of some classes of cubic graphs, Australas. J. Combin. 72 (2018) 376–404.
- 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 - 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 - 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 - 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 - D.B. West, Introduction to Graph Theory (Prentice Hall, New York, 2001).
Close