Some results on dominaion coloring and total domination coloring in graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Studies in Mathematics, University of Mysore, Mysuru-570006, India

2 Department of Mathematics, St. Joseph’s University, Bengaluru-560027, India

Abstract

A (proper) coloring of $G$ is said to be domination coloring if each vertex dominates at least one color class and each color class dominated by some vertex. The minimum number of colors required for a domination coloring of $G$ is called the domination chromatic number of $G$, and is denoted by $\chi_{dd}(G)$. For the graph $G$ without isolated vertices, domination coloring of $G$ is said to be the total domination coloring if each vertex dominates at least one color class contained in its open neighborhood. The minimum number of colors required for a total domination coloring of $G$ is called the total domination chromatic number, and is denoted by $\chi_{td}(G)$. In this paper, we have constructed graphs $G$ for arbitrary values of  $\chi(G)$ and $\chi_{dd}(G)$, as well as  $\chi(G)$ and $\chi_{td}(G)$. An upper bound for domination chromatic number (total domination chromatic number) in terms of dominated chromatic number and domination number (total domination number) is obtained. An upper bound for domination chromatic number in terms of maximum degree and order, as well as in terms of diameter of the graph is obtained. We have also characterized graphs of order $n$ with $\chi_{dom} = n-1$, $\chi_{dd} = 3$ and $\chi_{td} = 3$. 

Keywords

Main Subjects

References

[1] S. Arumugam, J. Bagga, and K.R. Chandrasekar, On dominator colorings in graphs, Proc. Math. Sci. 122 (2012), no. 4, 561–571. https://doi.org/10.1007/s12044-012-0092-5
[2] L.W. Beineke and R.J. Wilson, Topics in Chromatic Graph Theory, vol. 156, Cambridge University Press, 2015.
[3] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008.
[4] G. Chartrand and P. Zhang, Chromatic Graph Theory, Chapman and Hall/CRC, 2019.
[5] M. Chellali and F. Maffray, Dominator colorings in some classes of graphs, Graphs Combin. 28 (2012), no. 1, 97–107.
https://doi.org/10.1007/s00373-010-1012-z
[6] K.P. Chithra and M. Joseph, Total domination coloring of graphs, J. Math. Comput. Sci. 11 (2020), no. 1, 442–458.
https://doi.org/10.28919/jmcs/5073
[7] R. Gera, On dominator colorings in graphs, Graph Theory Notes 52 (2007), 25–30.
[8] R. Gera, C.W. Rasmussen, and S. Horton, Dominator colorings and safe clique partitions, Congr. Numer. 181 (2006), 19–32.
[9] F. Harary, Graph Theory, Narosa Publ., New Delhi, 2001.
[10] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graph, Marcel Dekker, New York, 1998.
[11] D.A. Kalarkop, A study on certain aspects in graph coloring and domination, Ph.d thesis, University of Mysore, 2023.
12] A.P. Kazemi, total dominator chromatic number, Trans. Comb. 4 (2015), no. 2, 57–68.
[13] A.P. Kazemi and F. Kazemnejad, Total dominator coloring of central graphs, Ars Combin. 155 (2021), 45–67.
[14] A.P. Kazemi and F. Kazemnejad, Total dominator total chromatic numbers of cycles and paths, RAIRO
Oper. Res. 57 (2023), no. 2, 383–399. https://doi.org/10.1051/ro/2022183
[15] A.P. Kazemi, F. Kazemnejad, and S. Moradi, Total dominator total coloring ofa graph, Contrib. Discrete Math. 18 (2023), no. 2, 1–19. https://doi.org/10.55016/ojs/cdm.v18i2.70912
[16] F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli, Total dominator coloring number of middle graphs, Discrete Math. Algorithms Appl. 15 (2023), no. 2, 2250076. https://doi.org/10.1142/S1793830922500768
[17] H.B. Merouane, M. Haddad, M. Chellali, and H. Kheddouci, Dominated colorings of graphs, Graphs Combin. 31 (2015), no. 3, 713–727. https://doi.org/10.1007/s00373-014-1407-3
[18] Y. Zhou, D. Zhao, M. Ma, and J. Xu, Domination coloring of graphs, Mathematics 10 (2022), no. 6, 998. https://doi.org/10.3390/math10060998
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 13 October 2025

Files

Share

How to cite

Statistics