Injective coloring of generalized Mycielskian of graphs

Document Type : Original paper

Authors

Department of Mathematics, National Institute of Technology Calicut, Kozhikode, India

Abstract

The injective chromatic number $\chi_i(G)$ of a graph $G$ is the smallest number of colors required to color the vertices of $G$ such that any two vertices with a common neighbor are assigned distinct colors. The Mycielskian or Mycielski graph $\mu(G)$ of a graph $G$, introduced by Jan Mycielski in 1955 has the property that, these graphs have large chromatic number with small clique number. The generalized Mycielskian $\mu_m(G),m>0$ (also known as cones over graphs) are the natural generalizations of the Mycielski graphs. In this paper, sharp bounds are obtained for the injective chromatic number of generalized Mycielskian of any graph $G$. Further, the injective chromatic number of generalized Mycielskian of some special classes of graphs such as paths, cycles, complete graphs, and complete bipartite graphs are obtained.

Keywords

Main Subjects

References

[1] O.V. Borodin and A.O. Ivanova, Injective $(\Delta + 1)$-coloring of planar graphs with girth 6, Sib. Math. J. 52 (2011), no. 1, 23–29.
https://doi.org/10.1134/S0037446606010034
[2] Y. Bu, D. Chen, A. Raspaud, and W. Wang, Injective coloring of planar graphs, Discrete Appl. Math. 157 (2009), no. 4, 663–672.
https://doi.org/10.1016/j.dam.2008.08.016
[3] Y. Bu and K. Lu, Injective coloring of planar graphs with girth 7, Discrete Math Algorithms Appl. 4 (2012), no. 2, Article ID: 1250034.
https://doi.org/10.1142/S1793830912500346
[4] Y. Bu, C. Qi, J. Zhu, and T. Xu, Injective coloring of planar graphs, Theor Comput Sci. 857 (2021), 114–122.
https://doi.org/10.1016/j.tcs.2021.01.007
[5] G. Fan, Circular chromatic number and Mycielski graphs, Combinatorica 24 (2004), no. 1, 127–135.
https://doi.org/10.1007/s00493-004-0008-9
[6] G. Hahn, J. Kratochvıl, J. Širáň, and D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002), no. 1-2, 179–192.
https://doi.org/10.1016/S0012-365X(01)00466-6
[7] F. Harary, Graph Theory, Addison-Wesley Pub. Co. Inc., Philippines, 1969.
[8] P. Hell, A. Raspaud, and J. Stacho, On injective colourings of chordal graphs, LATIN 2008: Theoretical Informatics (E.S. Laber, C. Bornstein, L.T. Nogueira, and L. Faria, eds.), Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 520–530.
[9] S.J. Kim and S. Oum, Injective chromatic number and chromatic number of the square of graphs, preprint (2009).
[10] A. Kishore and M.S. Sunitha, Injective chromatic sum and injective chromatic polynomials of graphs, Gen. Math. Notes 18 (2013), no. 2, 55–66.
[11] A. Kishore and M.S. Sunitha, On injective chromatic polynomials of graphs, Discrete Math. Algorithms Appl. 7 (2015), no. 3, Article ID: 1550035.
https://doi.org/10.1142/S1793830915500354
[12] M. Larsen, J. Propp, and D. Ullman, The fractional chromatic number of Mycielski’s graphs, J. Graph Theory 19 (1995), no. 3, 411–416.
https://doi.org/10.1002/jgt.3190190313
[13] D.D.F. Liu, Circular chromatic number for iterated Mycielski graphs, Discrete Math. 285 (2004), no. 1-3, 335–340.
https://doi.org/10.1016/j.disc.2004.01.020
[14] B. Lužar, R. Škrekovski, and M. Tancer, Injective colorings of planar graphs with few colors, Discrete Math. 309 (2009), no. 18, 5636–5649.
https://doi.org/10.1016/j.disc.2008.04.005
[15] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), no. 2, 161–162.
[16] P.R.J. ¨Ostergård, On a hypercube coloring problem, J. Comb. Theory Ser. A. 108 (2004), no. 2, 199–204.
https://doi.org/10.1016/j.jcta.2004.06.010
[17] B.S. Panda and Priyamvada, Injective coloring of some subclasses of bipartite graphs and chordal graphs, Discrete Appl. Math. 291 (2021), 68–87.
https://doi.org/10.1016/j.dam.2020.12.006
[18] J. Song and J. Yue, Injective coloring of some graph operations, Appl. Math. Comput. 264 (2015), 279–283.
https://doi.org/10.1016/j.amc.2015.03.124
[19] C. Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001), no. 2, 87–94.
https://doi.org/10.1002/jgt.1025
[20] V.J. Vernold and S. Ulagammal, On star coloring of degree splitting of wheel graph families and Mycielskian, Util. Math. 110 (2019).
[21] D.B. West, Introduction to Graph Theory, vol. 2, Prentice hall Upper Saddle River, New Jersey, 2001.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 10 December 2023

Files

Share

How to cite

Statistics