A Counterexample on the Conjecture and bounds on χ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=(V1,…,Vk) of G partitions the vertex set V(G) into independent sets Vi 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 Vi such that v is adjacent to all the vertices of Vi and v is said to have an anti-dominator (anti-dom) color class in C if there is color class Vj such that v is not adjacent to any vertex of Vj. 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 χ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 χ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 χgd(G)=2χ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