A Counterexample on the Conjecture and bounds on $\chi_{gd}$-number of Mycielskian of a graph

Document Type : Original paper

Authors

Department of Studies in Mathematics, University of Mysore, Manasagangothri, Mysuru – 570 006, India

Abstract

A coloring $C=(V_1, \dots, V_k)$ of $G$ partitions the vertex set $V(G)$ into independent sets $V_i$ which are said to be color classes with respect to the coloring $C$. A vertex $v$ is said to have a dominator (dom) color class in $C$ if there is color class $V_i$ such that $v$ is adjacent to all the vertices of $V_i$ and $v$ is said to have an anti-dominator (anti-dom) color class in $C$ if there is color class $V_j$ such that $v$ is not adjacent to any vertex of $V_j$. Dominator coloring of $G$ is a coloring $C$ of $G$ such that every vertex has a dom color class. The minimum number of colors required for a dominator coloring of $G$ is called the dominator chromatic number of $G$, denoted by $\chi_{d}(G)$. Global Dominator coloring of $G$ is a coloring $C$ of $G$ such that every vertex has a dom color class and an anti-dom color class. The minimum number of colors required for a global dominator coloring of $G$ is called the global dominator chromatic number of $G$, denoted by $\chi_{gd}(G)$. In this paper, we give a counterexample for the conjecture posed in [I. Sahul Hamid, M.Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39  (2019), 325--339] that for a graph $G$, if $\chi_{gd}(G)=2\chi_{d}(G)$, then $G$ is a complete multipartite graph. We deduce upper and lower bound for the global dominator chromatic number of Mycielskian of the graph $G$ in terms of dominator chromatic number of $G$.

Keywords

Main Subjects

References

[1] A.M. Abid and T.R. Ramesh Rao, Dominator coloring of Mycielskian graphs, Australas. J. Combin. 73 (2019), 274–279.
[2] S. Arumugam, J. Bagga, and K.R. Chandrasekar, On dominator colorings in graphs, Proc. Math. Sci. 122 (2012), no. 4, 561–571. http://doi.org/10.1007/s12044-012-0092-5
[3] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, second ed., Universitext, Springer, New York, 2012.
[4] S. Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math. 310 (2010), no. 3, 662–669.
[5] G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, sixth ed., Textbooks in Mathematics, CRC Press, Boca Raton, FL, 2016.
[6] X.G. Chen and H.M. Xing, Domination parameters in Mycielski graphs, Util. Math. 71 (2006), 235–244.
[7] R. Gera, C. Rasmussen, and S. Horton, Dominator colorings and safe clique partitions, Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 181, 2006, pp. 19–32.
[8] R.M. Gera, On dominator colorings in graphs, Graph Theory Notes N.Y. 52 (2007), 25–30.
[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[10] R. Rangarajan and D.A. Kalarkop, A note on global dominator coloring of graphs, Discrete Math. Algorithms Appl. 14 (2022), no. 5, Article ID: 2150158.  https://doi.org/10.1142/S1793830921501585
[11] I. Sahul Hamid and M. Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39 (2019), no. 2, 325–339.  http://doi.org/10.7151/dmgt.2089
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 197-204

Files

Share

How to cite

Statistics