Solving the dynamic coloring problem for direct products of paths with fan graphs

Raúl M. Falcón; S. Gowri; M. Venkatachalam

doi:10.2478/auom-2023-0006

.blurhash-client-img { display: none !important; }

Solving the dynamic coloring problem for direct products of paths with fan graphs

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

Volume 31 (2023): Issue 1 (January 2023)

By: Raúl M. Falcón, S. Gowri and M. Venkatachalam

Open Access

|Feb 2023

Abstract

This paper deals with the r-dynamic chromatic problem of the direct product of a path with a fan graph F_m,n. The problem is completely solved except for the case n<r ∈{2m +2, 2m +3}, which is solved under certain assumptions. It enables us to determine in particular the dynamic chromatic number concerning this problem, for all r ≤ 7, and also, for all m ∈{1, 2}.

References

[1] H. Agustin, D Dafik and A. Y. Harsya, On r-dynamic coloring of some graph operation,Int.J.Comb. 1 (2016), 22–30.
Search in Google Scholar Back to article
[2] A. Ahadi, S. Akbari, A. Dehghana and M. Ghanbari, On the difference between chromatic number and dynamic chromatic number of graphs,Discrete Math. 312 (2012), 2579–2583.10.1016/j.disc.2011.09.006
Search in Google Scholar Back to article
[3] S. Akbari, M. Ghanbari and S. Jahanbekam, On the dynamic chromatic number of graphs, in Combinatorics and graphs, Contemp. Math. 531 (2010), 11–18.10.1090/conm/531/10454
Search in Google Scholar Back to article
[4] S. Akbari, M. Ghanbari and S. Jahanbekam, On the dynamic coloring of Cartesian product graphs,Ars Comb. 114 (2014), 161–168.
Search in Google Scholar Back to article
[5] M. Alishahi, On the dynamic coloring of graphs, Discrete Appl. Math. 159 (2011), 152–156.10.1016/j.dam.2010.10.012
Search in Google Scholar Back to article
[6] M. Alishahi, Dynamic chromatic number of regular graphs, Discrete Appl. Math. 160 (2012), 2098–2103.10.1016/j.dam.2012.05.017
Search in Google Scholar Back to article
[7] 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, AIMSMath. 6 (2021), 1470–1496.
Search in Google Scholar Back to article
[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.
Search in Google Scholar Back to article
[9] 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 (2020), 6496–6520.10.3934/math.2020419
Search in Google Scholar Back to article
[10] R. M. Falcón, M. Venkatachalam, S. Gowri and G. Nandini, On the r-dynamic coloring of some fan graph families, Analele Stiint. ale Univ. Ovidius Constanta Ser. Mat. 29 (2021), 151–181.
Search in Google Scholar Back to article
[11] R. M. Falcón, M. Venkatachalam, S. Gowri and G. Nandini, On the r-dynamic coloring of the direct product of a path and a k-subdivision of a star graph, Discrete Math. Algorithms Appl., 14 (2022), paper 2150121, 19 pages.10.1142/S1793830921501214
Search in Google Scholar Back to article
[12] S. Gowri, M. Venkatachalam, V. N. Mishra and L. N. Mishra, On r-dynamic coloring of double star graph families, Palest. J. Math. 10 (2021), 53–62.
Search in Google Scholar Back to article
[13] F. Harary, Graph Theory, Reading, Massachusetts, Addison Wesley, 1969.10.21236/AD0705364
Search in Google Scholar Back to article
[14] H. J. Lai, B. Montgomery and H. Poon, Upper bounds of dynamic chromatic number,Ars Comb. 68 (2003), 193–201.
Search in Google Scholar Back to article
[15] H. J. Lai, B. Montgomery and Z. Tao, Conditional colorings of graphs, Discrete Math. 306 (2006), 1997–2004.10.1016/j.disc.2006.03.052
Search in Google Scholar Back to article
[16] K. Kaliraj, H. N. Kumar and J. V. Vivin, On dynamic colouring of Cartesian product of complete graph with some graphs, J. Taibah Univ. Sci. 14 (2020), 168–171.10.1080/16583655.2020.1713586
Search in Google Scholar Back to article
[17] 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), 2050019.10.1142/S1793830920500196
Search in Google Scholar Back to article
[18] N. Mohanapriya, J. V. Vivin and M. Venkatachalam, On dynamic coloring of fan graphs, Int. J. Pure Appl. Math. 106 (2016), 169–174.
Search in Google Scholar Back to article
[19] B. Montgomery, Dynamic coloring of graphs, PhD Thesis, West Virginia University, ProQuest LLC, Ann Arbor, MI, 2001.
Search in Google Scholar Back to article
[20] 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 (2019), 923–928.10.31801/cfsuasmas.489727
Search in Google Scholar Back to article
[21] G. Nandini, M. Venkatachalam and R. M. Falcón, On the r-dynamic coloring of subdivision-edge coronas of a path, AIMS Math. 5 (2020), 4546–4562.10.3934/math.2020292
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/auom-2023-0006 | Journal eISSN: 1844-0835 | Journal ISSN: 1224-1784

Journal RSS Feed

Language: English

Page range: 115 - 142

Submitted on: Jan 5, 2022

Accepted on: Jul 4, 2022

Published on: Feb 4, 2023

Published by: Ovidius University of Constanta

In partnership with: Paradigm Publishing Services

Publication frequency: 3 issues per year

Keywords:

Dynamic coloring problem,

path,

Related subjects:

© 2023 Raúl M. Falcón, S. Gowri, M. Venkatachalam, published by Ovidius University of Constanta
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 31 (2023): Issue 1 (January 2023)