A Survey on Packing Colorings

Brešar, Boštjan ; Ferme, Jasmina ; Klavžar, Sandi ; Rall, Douglas F.

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 923-970.

Résumé

If S = (a1, a2, . . .) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1, X2, . . . such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V (G) = X1 ∪ ∪ Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai = i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and its generalization, the S-packing coloring. We also list several conjectures and open problems.

Détail

Keywords: packing coloring, packing chromatic number, subcubic graph, S -packing chromatic number, computational complexity

Bibliographie

[1] G. Argiroffo, G. Nasini and P. Torres, The packing coloring problem (q, q − 4) graphs, Lecture Notes in Comput. Sci. 7422 (2012) 309–319. doi:10.1007/978-3-642-32147-4_28

[2] G. Argiro o, G. Nasini and P. Torres, The packing coloring problem for lobsters and partner limited graphs, Discrete Appl. Math. 164 (2014) 373–382. doi:10.1016/j.dam.2012.08.008

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

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

[5] O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud and É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77–89. doi:10.1016/S0012-365X(98)00393-8

[6] D. Božović and I. Peterin, A note on the packing chromatic number of lexicographic products. arXiv:1909.11325 [math.CO] (25 Sep. 2019)

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

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

[9] B. Brešar and J. Ferme, Graphs that are critical for the packing chromatic number, Discuss. Math. Graph Theory (2020), in press. doi:10.7151/dmgt.2298

[10] B. Brešar, N. Gastineau and O. Togni, Packing colorings of subcubic outerplanar graphs, Aequationes Math., to appear.

[11] B. Brešar, S. Klavžar and D.F. Rall, Packing chromatic number of base-3 Sierpiński graphs, Graphs Combin. 32 (2016) 1313–1327. doi:10.1007/s00373-015-1647-x

[12] 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. doi:10.1016/j.dam.2007.06.008

[13] 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. doi:10.1016/j.disc.2016.09.030

[14] 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. doi:10.1007/s00010-016-0461-8

[15] 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. doi:10.1007/s00010-017-0520-9

[16] D.W. Cranston and S.-J. Kim, List-coloring the square of a subcubic graph, J. Graph Theory 57 (2008) 65–87. doi:10.1002/jgt.20273

[17] J. Czap and S. Jendrol’, Facial packing edge-coloring of plane graphs, Discrete Appl. Math. 213 (2016) 71–75. doi:10.1016/j.dam.2016.05.010

[18] J. Czap, S. Jendroľ, P.Šugerek and J. Valiska, Facial packing vertex-coloring of subdivided plane graphs, Discrete Appl. Math. 257 (2019) 95–100. doi:10.1016/j.dam.2018.10.022

[19] F. Deng, Z. Shao and A. Vesel, On the packing coloring of base-3 Sierpiński and H graphs. arXiv:1909.08285 [math.CO] (18 Sep. 2018)

[20] D.D. Durgun and H.B. Ozen Dortok, Packing chromatic number of transformation graphs, Thermal Sci. 23 (2019) S1991–S1995. doi:10.2298/TSCI190720363D

[21] J. Ekstein, J. Fiala, P. Holub and B. Lidický, The packing chromatic number of the square lattice is at least 12. arXiv:1003.2291 [cs.DM] (11 Mar 2010)

[22] J. Ekstein, P. Holub and B. Lidický, Packing chromatic number of distance graphs, Discrete Appl. Math. 160 (2012) 518–524. doi:10.1016/j.dam.2011.11.022

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

[24] G. Fertin, E. Godard and A. Raspaud, Acyclic and k-distance coloring of the grid, Inform. Process. Lett. 87 (2003) 51–58. doi:10.1016/S0020-0190(03)00232-1

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

[26] J. Fiala, S. Klavžar and B. Lidický, The packing chromatic number of infinite product graphs, European J. Combin. 30 (2009) 1101–1113. doi:10.1016/j.ejc.2008.09.014

[27] A. Finbow and D.F. Rall, On the packing chromatic number of some lattices, Discrete Appl. Math. 158 (2010) 1224–1228. doi:10.1016/j.dam.2009.06.001

[28] J. Fresán-Figueroa, D. González-Moreno and M. Olsen, On the packing chromatic number of Moore graphs. arXiv:1909.11638 [math.CO] (25 Sep 2019)

[29] N. Gastineau, Dichotomies properties on computational complexity of S-packing coloring problems, Discrete Math. 338 (2015) 1029–1041. doi:10.1016/j.disc.2015.01.028

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

[31] N. Gastineau, H. Kheddouci and O. Togni, Subdivision into i-packings and S-packing chromatic number of some lattices, Ars Math. Contemp. 9 (2015) 321–344. doi:10.26493/1855-3974.436.178

[32] N. Gastineau and O. Togni, S-packing colorings of cubic graphs, Discrete Math. 339 (2016) 2461–2470. doi:10.1016/j.disc.2016.04.017

[33] N. Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019) 63–75. doi:10.1016/j.dam.2018.12.035

[34] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B 16 (1974) 47–56. doi:10.1016/0095-8956(74)90094-X

[35] 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.

[36] W. Goddard and H. Xu, The S-packing chromatic number of a graph, Discuss. Math. Graph Theory 32 (2012) 795–806. doi:10.7151/dmgt.1642

[37] W. Goddard and H. Xu, A note on S-packing colorings of lattices, Discrete Appl. Math. 166 (2014) 255–262. doi:10.1016/j.dam.2013.09.016

[38] J. Hagauer and S. Klavžar, On independence numbers of the Cartesian product of graphs, Ars Combin. 43 (1996) 149–157.

[39] A.M. Hinz, S. Klavžar and S.S. Zemljič, A survey and classification of Sierpiński-type graphs, Discrete Appl. Math. 217 (2017) 565–600. doi:10.1016/j.dam.2016.09.024

[40] P. Holub, M. Jakovac and S. Klavžar, S-packing chromatic vertex-critical graphs. arXiv:2001.09362v1 [math.CO] (28 Jan 2020)

[41] Y. Jacobs, E. Jonck and E.J. Joubert, A lower bound for the packing chromatic number of the Cartesian product of cycles, Cent. Eur. J. Math. 11 (2013) 1344–1357. doi:10.2478/S11533-013-0237-5

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

[43] S. Klavžar and U. Milutinović, Graphs S(n, k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47 (1997) 95–104. doi:10.1023/A:1022444205860

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

[45] D. Korže and A. Vesel, On the packing chromatic number of square and hexagonal lattice, Ars Math. Contemp. 7 (2014) 13–22. doi:10.26493/1855-3974.255.88d

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

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

[48] D. Korže, Ž. Markuš and A. Vesel, A heuristic approach for searching (d, n)-packing colorings of infinite lattices, Discrete Appl. Math. 257 (2019) 353–358. doi:10.1016/j.dam.2018.09.018

[49] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008) 422–426. doi:10.1016/j.disc.2006.11.059

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

[51] D. Laïche, I. Bouchemakh and É. Sopena, On the packing coloring of undirected and oriented generalized theta graphs, Australas. J. Combin. 66 (2016) 310–329.

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

[53] R. Lemdani, M. Abbas and J. Ferme, Packing chromatic numbers of finite super subdivisions of graphs, Filomat, to appear.

[54] R. Liu, X. Liu, M. Rolek and G. Yu, Packing (1, 1, 2, 2)-coloring of some subcubic graphs, Discrete Appl. Math. (2020), in press. doi:10.1016/j.dam.2020.03.015

[55] 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. doi:/10.1016/j.dam.2017.03.013

[56] G. Nasini, D. Severin and P. Torres, On the packing chromatic number on Hamming graphs and general graphs . arXiv:1510.05524 [cs.DM] (19 Oct 2015)

[57] K. Rajalakshmi and M. Venkatachalam, On packing coloring of double wheel graph families, Int. J. Pure Appl. Math. 119 (2018) 2389–2396.

[58] K. Rajalakshmi and M. Venkatachalam On packing coloring of helm related graphs, J. Discrete Math. Sci. Cryptogr. 22 (2019) 989–1005. doi:10.1080/09720529.2019.1640968

[59] S. Roy, Packing chromatic number of certain fan and wheel related graphs, AKCE Int. J. Graphs Comb. 14 (2017) 63–69. doi:10.1016/j.akcej.2016.11.001

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

[61] Z. Shao and A. Vesel, Corrigendum to ‘Modeling the packing coloring problem of graphs’ [Appl. Math. Model. 39 (2015) 3588–3595], Appl. Math. Model. 40 (2016) 1683. doi:10.1016/j.apm.2015.08.001

[62] C. Sloper, An eccentric coloring of trees, Australas. J. Combin. 29 (2004) 309–321.

[63] R. Soukal and P. Holub, A note on packing chromatic number of the square lattice, Electron. J. Combin. 17 (2010) #N17. doi:10.37236/466

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

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

[66] V.G. Vizing, The Cartesian product of graphs, Vycisl. Sistemy 9 (1963) 30–43.

[67] A. William, S. Roy and I. Rajasingh, Packing chromatic number of cycle related graphs, Internat. J. Math. Soft Comput. 4 (2014) 27–33. doi:10.26708/IJMSC.2014.1.4.04

[68] A. William and S. Roy, Packing chromatic number of certain graphs, Int. J. Pure Appl. Math. 87 (2013) 731–739. doi:10.12732/ijpam.v87i6.1