×

Independence number and packing coloring of generalized Mycielski graphs. (English) Zbl 1459.05230

Summary: For a positive integer \(k \geq 1\), a graph \(G\) with vertex set \(V\) is said to be \(k\)-packing colorable if there exists a mapping \(f : V \mapsto \{1, 2, \dots, 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 \(\chi_\rho (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 \(\mu_m (G)\). We first give an explicit formula for \(\alpha (\mu_m (G))\) when \(m\) is odd and bounds when \(m\) is even. We then use these results to give exact values of \(\alpha(\mu_m (K_n))\) for any \(m\) and \(n\). Next, we give bounds on the packing chromatic number, \( \chi_\rho \), of \(\mu_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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C12 Distance in graphs

References:

[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 · Zbl 1370.05163
[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 · Zbl 1288.05078
[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 · Zbl 1376.05047
[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 · Zbl 1388.05059
[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 · Zbl 1400.05079
[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 · Zbl 1126.05045
[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 · Zbl 1342.05111
[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 · Zbl 1355.05194
[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 · Zbl 1357.05037
[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 · Zbl 1390.05186
[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 · Zbl 1121.05047
[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 · Zbl 1284.05213
[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 · Zbl 1219.05185
[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 · Zbl 1207.05165
[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 · Zbl 1221.05137
[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 · Zbl 0906.05043
[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 · Zbl 1339.05134
[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. · Zbl 1224.05172
[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 · Zbl 1256.05131
[22] L. Huang and G.J. Chang, The circular chromatic number of the Mycielskian of G^d_k, J. Graph Theory 32 (1999) 63-71. doi:10.1002/(SICI)1097-0118(199909)32:1〈63::AID-JGT6〉3.0.CO;2-B · Zbl 0928.05019
[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 · Zbl 1266.05121
[24] D. Korže and A. Vesel, On the packing chromatic number of square and hexagonal lattice, Ars Math. Contemp. 7 (2014) 13-22. · Zbl 1302.05142
[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. · Zbl 1375.05094
[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 · Zbl 0830.05027
[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 · Zbl 1211.05044
[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 · Zbl 1093.05050
[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 · Zbl 1361.05051
[30] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161-162. doi:10.4064/cm-3-2-161-162 · Zbl 0064.17805
[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 · Zbl 1496.05043
[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 · Zbl 1443.05077
[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 · Zbl 1215.05050
[34] O. Togni, On packing colorings of distance graphs, Discrete Appl. Math. 167 (2014) 280-289. doi:10.1016/j.dam.2013.10.026 · Zbl 1284.05109
[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 · Zbl 1316.05050
[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 · Zbl 1411.05092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.