Geodesic
Independence Number and Packing Coloring of Generalized Mycielski Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 725-747.

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

For a positive integer k ⩾ 1, a graph G with vertex set V is said to be k-packing colorable if there exists a mapping f : V ↦ 1, 2, . . ., k such that any two distinct vertices x and y with the same color f(x) = f(y) are at distance at least f(x) + 1. The packing chromatic number of a graph G, denoted by χρ(G), is the smallest integer k such that G is k-packing colorable. In this work, we study both independence and packing colorings in the m-generalized Mycielskian of a graph G, denoted μm(G). We first give an explicit formula for α (μm(G)) when m is odd and bounds when m is even. We then use these results to give exact values of α(μm(Kn)) for any m and n. Next, we give bounds on the packing chromatic number, χρ, of μm(G). We also prove the existence of large planar graphs whose packing chromatic number is 4. The rest of the paper is focused on packing chromatic numbers of the Mycielskian of paths and cycles.
Keywords: independence number, packing chromatic number, Mycielskians, generalized Mycielskians 
@article{DMGT_2021_41_3_a2,
     author = {Bidine, Ez Zobair and Gadi, Taoufiq and Kchikech, Mustapha},
     title = {Independence {Number} and {Packing} {Coloring} of {Generalized} {Mycielski} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {725--747},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/}
}
TY  - JOUR
AU  - Bidine, Ez Zobair
AU  - Gadi, Taoufiq
AU  - Kchikech, Mustapha
TI  - Independence Number and Packing Coloring of Generalized Mycielski Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 725
EP  - 747
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/
LA  - en
ID  - DMGT_2021_41_3_a2
ER  - 
%0 Journal Article
%A Bidine, Ez Zobair
%A Gadi, Taoufiq
%A Kchikech, Mustapha
%T Independence Number and Packing Coloring of Generalized Mycielski Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 725-747
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/
%G en
%F DMGT_2021_41_3_a2
Bidine, Ez Zobair; Gadi, Taoufiq; Kchikech, Mustapha. Independence Number and Packing Coloring of Generalized Mycielski Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 725-747. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/

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

[2] G. Argiroffo, G. Nasini and P. Torres, The packing coloring problem for lobsters and partner limited graphs, Discrete Appl. Math. (2014) 164 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. (2018) 341 474–483. doi:10.1016/j.disc.2017.09.014

[4] 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

[5] 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

[6] 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

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

[8] 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

[9] 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

[10] 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

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

[12] T. Doslić, Mycielskians and matchings, Discuss. Math. Graph Theory 25 (2005) 261–266. doi:10.7151/dmgt.1279

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

[14] 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

[15] 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

[16] 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

[17] A.S. 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

[18] D.C. Fisher, P.A. McKenna and E.D. Boyer, Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski’s graphs, Discrete Appl. Math. 84 (1998) 93–105. doi:10.1016/S0166-218X(97)00126-1

[19] 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

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

[21] L. Guo, R. Liu, and X. Guo, Super connectivity and super edge connectivity of the Mycielskian of a graph, Graphs Combin. 28 (2012) 143–147. doi:10.1007/s00373-011-1032-3

[22] L. Huang and G.J. Chang, The circular chromatic number of the Mycielskian of Gdk, J. Graph Theory 32 (1999) 63–71. doi:10.1002/(SICI)1097-0118(199909)32:1〈63::AID-JGT6〉3.0.CO;2-B

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

[24] D. Korže and A. Vesel, On the packing chromatic number of square and hexagonal lattice, Ars Math. Contemp. 7 (2014) 13–22.

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

[26] M. Larsen, J. Propp and D. Ullman, The fractional chromatic number of Mycielski’s graphs, J. Graph Theory 19 (1995) 411–416. doi:10.1002/jgt.3190190313

[27] W. Lin, D. Der-Fen Liu and X. Zhu, Multi-coloring the Mycielskian of graphs, J. Graph Theory 63 (2010) 311–323. doi:10.1002/jgt.20429

[28] W. Lin, J. Wu, P.C. Lam and G. Gu, Several parameters of generalized Mycielskians, Discrete Appl. Math. 154 (2006) 1173–1182. doi:10.1016/j.dam.2005.11.001

[29] 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

[30] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161–162. doi:10.4064/cm-3-2-161-162

[31] KS. Savitha, MR. Chithra and A. Vijayakumar, Some diameter notions of the generalized Mycielskian of a graph, in: International Conference on Theoretical Computer Science and Discrete Mathematics 2016, Lecture Notes in Comput. Sci. 10398 (2017) 371–382. doi:10.1007/978-3-319-64419-6 48

[32] 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

[33] 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

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

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

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