The r-dynamic chromatic number of the corona product of graphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Annamalai University, Annamalainagar - 608 002, India

Abstract

Let G be a graph. An {\it r-dynamic k-coloring} of G is a proper k-coloring of G such that every vertex v in V(G) has neighbors in at least min{r,dG(v)} different color classes. The {\it r-dynamic chromatic number} of G, denoted by χr(G), is the least k such that G has an r-dynamic k-coloring. We determine the r-dynamic chromatic number of the corona product G⊙H of graphs G and H, in terms of the dynamic chromatic numbers of G and H.

Keywords

Main Subjects

References

1] I.H. Agustin, D.A.R. Wardani, B.J. Septory, A.I. Kristiana, and E.Y. Kurniawati, The r-dynamic chromatic number of corona of order two of any graphs with complete graph, J. Phys. Conf. Ser. 1306 (2019), no. 1, Article ID: 012046.
[2] A. Ahadi, S. Akbari, A. Dehghan, and M. Ghanbari, On the difference between chromatic number and dynamic chromatic number of graphs, Discrete Math. 312 (2012), no. 17, 2579–2583. https://doi.org/10.1016/j.disc.2011.09.006
[3] S. Akbari, M. Ghanbari, and S. Jahanbakam, On the dynamic chromatic number of graphs, Contemp. Math. 531 (2010), 11–18.
[4] S. Akbari, M. Ghanbari, and S. Jahanbekam, On the dynamic coloring of Cartesian product graphs., Ars Combin. 114 (2014), 161–168.
[5] S. Akbari, M. Ghanbari, and S. Jahanbekam, On the dynamic coloring of strongly regular graphs, Ars Combin. 113
(2014), 205–210.
[6] M. Alishahi, Dynamic chromatic number of regular graphs, Discrete Appl. Math. 160 (2012), no. 15, 2098–2103. https://doi.org/10.1016/j.dam.2012.05.017
[7] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Springer Science & Business Media, 2012.
[8] N. Bowler, J. Erde, F. Lehner, M. Merker, M. Pitz, and K. Stavropoulos, A counterexample to Montgomery’s conjecture on dynamic colourings of regular graphs, Discrete Appl. Math. 229 (2017), 151–153. https://doi.org/10.1016/j.dam.2017.05.004
[9] Y. Chen, S. Fan, H.J. Lai, H. Song, and L. Sun, On dynamic coloring for planar graphs and graphs of higher genus, Discrete Appl. Math. 160 (2012), no. 7-8, 1064–1071. https://doi.org/10.1016/j.dam.2012.01.012
[10] A. Dehghan and A. Ahadi, Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number, Discrete Appl. Math. 160 (2012), no. 15, 2142–2146. https://doi.org/10.1016/j.dam.2012.05.003
[11] R. Frucht and F. Harary, On the corona of two graphs, Aeq. Math. 4 (1970), 322–325. https://doi.org/10.1007/BF01844162
[12] H. Furma´nczyk, J.V. Vivin, and N. Mohanapriya, r-dynamic chromatic number of some line graphs, Indian J. Pure Appl. Math. 49 (2018), no. 4, 591–600. https://doi.org/10.1007/s13226-018-0288-1
[13] S. Jahanbekam, J. Kim, O. Suil, and D.B. West, On r-dynamic coloring of graphs, Discrete Appl. Math. 206 (2016), 65–72. https://doi.org/10.1016/j.dam.2016.01.016
[14] R. Kang, T. M¨uller, and D.B. West, On r-dynamic coloring of grids, Discrete Appl. Math. 186 (2015), 286–290. https://doi.org/10.1016/j.dam.2015.01.020
[15] S.J. Kim, S.J. Lee, and W.J. Park, Dynamic coloring and list dynamic coloring of planar graphs, Discrete Appl. Math. 161 (2013), no. 13-14, 2207–2212. https://doi.org/10.1016/j.dam.2013.03.005
[16] A.I. Kristiana, Dafik, M.I. Utoyo, and I.H. Agustin, On r-dynamic chromatic number of the corronation of path and several graphs, Int. J. Adv. Eng. Res. Sci. 4 (2017), no. 4, 96–101. https://dx.doi.org/10.22161/ijaers.4.4.13
[17] A.I. Kristiana and M.I. Utoyo, On the r-dynamic chromatic number of the corronation by complete graph, J. Phys. Conf. Ser. 1008 (2018), no. 1, Article ID: 012033.
[18] A.I. Kristiana, M.I. Utoyo, R. Alfarisi, and Dafik, r-dynamic coloring of the corona product of graphs, Discrete Math. Algorithms Appl. 12 (2020), no. 2, Article ID: 2050019. https://doi.org/10.1142/S1793830920500196
[19] A.I. Kristiana, M.I. Utoyo, and Dafik, The lower bound of the r-dynamic chromatic number of corona product by wheel graphs, AIP Conf. Proc. 2014 (2018), no. 1, Article ID: 020054.
[20] H.J. Lai, B. Montgomery, and H. Poon, Upper bounds of dynamic chromatic number, Ars Combin. 68 (2003), no. 3, 193–201.
[21] X. Li, X. Yao, W. Zhou, and H. Broersma, Complexity of conditional colorability of graphs, Appl. Math. Lett. 22 (2009), no. 3, 320–324. https://doi.org/10.1016/j.aml.2008.04.003
[22] X. Li and W. Zhou, The 2nd-order conditional 3-coloring of claw-free graphs, Theoret. Comput. Sci. 396 (2008), no. 1-3, 151–157.  https://doi.org/10.1016/j.tcs.2008.01.034
[23] B. Montgomery, Dynamic Coloring of Graphs, West Virginia University, 2001.
[24] B.J. Septory, A.I. Kristiana, I.H. Agustin, and D.A.R. Wardani, On r-dynamic chromatic number of coronation of order two of any graphs with path graph, IOP Conf. Ser.: Earth Environ. Sci. 243 (2019), no. 1, Article ID: 012113. https://doi.org/10.1088/1755-1315/243/1/012113
[25] A. Taherkhani, On r-dynamic chromatic number of graphs, Discrete Appl. Math. 201 (2016), 222–227. https://doi.org/10.1016/j.dam.2015.07.019
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 03 February 2025

Files

Share

How to cite

Statistics