Article in press
Authors:
Raghavendra Rao B.V.
Department of Computer Science
IIT Madras
Chennai
600036
email: bvrr@cse.iitm.ac.in
Title:
Bounds for packing chromatic number of some subclasses of trees
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-01-18 , Revised: 2025-07-02 , Accepted: 2025-07-02 , Available online: 2025-08-29 , https://doi.org/10.7151/dmgt.2597
Abstract:
It is known that computing packing chromatic number is \NP-hard even for trees.
In this article, we derive an exact formula for the packing chromatic number
for trees of diameter five in terms of number of vertices of degree at least
four. Additionally, we improve the upper bound for shifted packing
chromatic number of an infinite path. We also establish a new bound for the
packing chromatic number of any tree, related to the number of vertices of
degree at least four. Finally, we identify an infinite class of trees containing
caterpillars, which has a bounded packing chromatic number.
Keywords:
tree, vertex degree, graph diameter, graph coloring
References:
- G. Argiroffo, G. Nasini and P. Torres, The packing coloring problem for lobsters and partner limited graphs, Discrete Appl. Math. 164 (2014) 373–382.
https://doi.org/10.1016/j.dam.2012.08.008 - 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 - 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 and J. Ferme, Graphs that are critical for the packing chromatic number, Discuss. Math. Graph Theory 42 (2022) 569–589.
https://doi.org/10.7151/dmgt.2298 - B. Brešar, J. Ferme, S. Klavžar and D.F. Rall, A survey on packing colorings, Discuss. Math. Graph Theory 40 (2020) 923–970.
https://doi.org/10.7151/dmgt.2320 - B. Brešar, S. Klavžar and D.F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math. 155 (2007) 2303–2311.
https://doi.org/10.1016/j.dam.2007.06.008 - B. Brešar, S. Klavžar, D.F. Rall and K. Wash, Packing chromatic number, $(1, 1, 2, 2)$-colorings, and characterizing the Petersen graph, Aequationes Math. 91 (2017) 169–184.
https://doi.org/10.1007/s00010-016-0461-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 - J. Fiala, S. Klavžar and B. Lidick\`y, The packing chromatic number of infinite product graphs, European J. Combin. 30 (2009) 1101–1113.
https://doi.org/10.1016/j.ejc.2008.09.014 - 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–50.
- D. Laïche and É. Sopena, Packing colouring of some classes of cubic graphs, Australas. J. Combin. 72 (2018) 376–404.
- C. Sloper, An eccentric coloring of trees, Australas. J. Combin. 29 (2004) 309–322.
- D.B. West, Introduction to Graph Theory (Prentice Hall, 2001).
Close