Revista de la
Unión Matemática Argentina
The $r$-dynamic edge coloring of a closed helm graph
Raúl M. Falcón, Mathiyazhagan Venkatachalam, Sathasivam Gowri, and Gnanasekaran Nandini

Volume 65, no. 2 (2023), pp. 331–346    

Published online: November 22, 2023

https://doi.org/10.33044/revuma.2669

Download PDF

Abstract

As a natural generalization of the classical coloring problem in graph theory, the dynamic coloring problem deals with the existence of a proper coloring $c$ of a graph so that $|c(N(v))| \geq \min\{r, d(v)\}$ for every vertex $v$. In this paper, we obtain the $r$-dynamic edge chromatic number of any given closed helm graph for any positive integer $r$. This coincides with the $r$-dynamic chromatic number of the line graph of a closed helm graph.

References

  1. A. Ahadi, S. Akbari, A. Dehghan, and M. Ghanbari, On the difference between chromatic number and dynamic chromatic number of graphs, Discrete Math. 312 no. 17 (2012), 2579–2583.  DOI  MR  Zbl
  2. S. Akbari, M. Ghanbari, and S. Jahanbekam, On the list dynamic coloring of graphs, Discrete Appl. Math. 157 no. 14 (2009), 3005–3007.  DOI  MR  Zbl
  3. S. Akbari, M. Ghanbari, and S. Jahanbekam, On the dynamic chromatic number of graphs, in Combinatorics and Graphs, Contemp. Math. 531, Amer. Math. Soc., Providence, RI, 2010, pp. 11–18.  DOI  MR  Zbl
  4. M. Alishahi, On the dynamic coloring of graphs, Discrete Appl. Math. 159 no. 2-3 (2011), 152–156.  DOI  MR  Zbl
  5. M. Alishahi, Dynamic chromatic number of regular graphs, Discrete Appl. Math. 160 no. 15 (2012), 2098–2103.  DOI  MR  Zbl
  6. T. Deepa, R. M. Falcón, and M. Venkatachalam, On the $r$-dynamic coloring of the direct product of a path with either a complete graph or a wheel graph, AIMS Math. 6 no. 2 (2021), 1470–1496.  DOI  MR  Zbl
  7. T. Deepa, M. Venkatachalam, and R. M. Falcón, On the $r$-dynamic coloring of the direct product of a path with either a path or a cycle, AIMS Math. 5 no. 6 (2020), 6496–6520.  DOI  MR  Zbl
  8. T. Deepa and M. Venkatachalam, On $r$-dynamic coloring of the total graphs of gear graphs, Appl. Math. E-Notes 18 (2018), 69–81.  MR  Zbl Available at https://www.math.nthu.edu.tw/~amen/2018/AMEN-170730.pdf.
  9. H. Furmańczyk, J. Vernold Vivin, and N. Mohanapriya, $r$-dynamic chromatic number of some line graphs, Indian J. Pure Appl. Math. 49 no. 4 (2018), 591–600.  DOI  MR  Zbl
  10. F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969.  MR  Zbl
  11. S. Jahanbekam, J. Kim, S. O, and D. B. West, On $r$-dynamic coloring of graphs, Discrete Appl. Math. 206 (2016), 65–72.  DOI  MR  Zbl
  12. R. Kang, T. Müller, and D. B. West, On $r$-dynamic coloring of grids, Discrete Appl. Math. 186 (2015), 286–290.  DOI  MR  Zbl
  13. H.-J. Lai, B. Montgomery, and H. Poon, Upper bounds of dynamic chromatic number, Ars Combin. 68 (2003), 193–201.  MR  Zbl
  14. X. Li and W. Zhou, The 2nd-order conditional 3-coloring of claw-free graphs, Theoret. Comput. Sci. 396 no. 1-3 (2008), 151–157.  DOI  MR  Zbl
  15. S. Loeb, T. Mahoney, B. Reiniger, and J. Wise, Dynamic coloring parameters for graphs with given genus, Discrete Appl. Math. 235 (2018), 129–141.  DOI  MR  Zbl
  16. I. N. Maylisa, D. Dafik, and S. Setiawani, Keterampilan berpikir tingkat tinggi dalam pewarnaan sisi $r$-dinamis pada graf khusus, Kadikma 6 no. 3 (2015), 132–141. Available at https://jurnal.unej.ac.id/index.php/kadikma/article/view/5218.
  17. D. E. W. Meganingtyas, Analisis pewarnaan $r$-dinamis pada graf-graf khusus, Master's thesis, Universitas Jember, Indonesia, 2015. Available at https://repository.unej.ac.id/handle/123456789/73165.
  18. L. D. Minarti, D. Dafik, S. Setiawani, S. Slamin, and A. Fatahillah, Pewarnaan sisi $r$-dinamis pada graf hasil operasi amalgamasi titik keluarga graf pohon dan kaitannya dengan keterampilan berpikir tingkat tinggi, Saintifika 21 no. 2 (2019), 15–22. Available at https://jurnal.unej.ac.id/index.php/STF/article/view/13561.
  19. N. Mohanapriya, V. J. Vernold, and M. Venkatachalam, On dynamic coloring of fan graphs, Int. J. Pure Appl. Math. 106 no. 8 (2016), 169–174. Available at https://acadpubl.eu/jsi/2016-106-6-7-8/2016-106-8/20/index.html.
  20. N. Mohanapriya, J. Vernold Vivin, and M. Venkatachalam, $\delta$-dynamic chromatic number of Helm graph families, Cogent Math. 3 (2016), Art. ID 1178411, 4 pp.  DOI  MR  Zbl
  21. B. Montgomery, Dynamic coloring of graphs, Ph.D. thesis, West Virginia University, 2001.  DOI  MR
  22. G. Nandini, M. Venkatachalam, and R. M. Falcón, On the $r$-dynamic coloring of subdivision-edge coronas of a path, AIMS Math. 5 no. 5 (2020), 4546–4562.  DOI  MR  Zbl
  23. G. Nandini, M. Venkatachalam, and S. Gowri, On $r$-dynamic coloring of the family of bistar graphs, Commun. Fac. Sci. Univ. Ank. Ser. A1. Math. Stat. 68 no. 1 (2019), 923–928.  DOI  MR  Zbl
  24. J. V. Vivin, N. Mohanapriya, J. Kok, and M. Venkatachalam, On dynamic coloring of certain cycle-related graphs, Arab. J. Math. (Springer) 9 no. 1 (2020), 213–221.  DOI  MR  Zbl