Geodesic
Global dominated coloring of graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1293-1309 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In this paper, we initiate a study of global dominated coloring of graphs as a variation of dominated colorings. A global dominated coloring of a graph G is a proper coloring such that for each color class there are at least two vertices, one of which is adjacent to all the vertices of this class while the other one is not adjacent to any vertex of the class. The global dominated chromatic number of G is the minimum number of colors used among all global dominated colorings of G. In this paper, we establish various bounds on the global dominated chromatic number of a graph in terms of some graph invariants including the order, dominated chromatic number, domination number and total domination number. Moreover, characterizations of extremal graphs attaining some of these bounds are provided. We also discuss the global dominated coloring in trees and split graphs.
Keywords: global dominated coloring, dominated coloring, dominated chromatic number 
@article{DMGT_2024_44_4_a3,
     author = {Kalarkop, David A. and Sahul Hamid, Ismail and Chellali, Mustapha and Rangarajan, R.},
     title = {Global dominated coloring of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1293--1309},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a3/}
}
TY  - JOUR
AU  - Kalarkop, David A.
AU  - Sahul Hamid, Ismail
AU  - Chellali, Mustapha
AU  - Rangarajan, R.
TI  - Global dominated coloring of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1293
EP  - 1309
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a3/
LA  - en
ID  - DMGT_2024_44_4_a3
ER  - 
%0 Journal Article
%A Kalarkop, David A.
%A Sahul Hamid, Ismail
%A Chellali, Mustapha
%A Rangarajan, R.
%T Global dominated coloring of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1293-1309
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a3/
%G en
%F DMGT_2024_44_4_a3
Kalarkop, David A.; Sahul Hamid, Ismail; Chellali, Mustapha; Rangarajan, R. Global dominated coloring of graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1293-1309. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a3/

[1] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249. https://doi.org/10.1002/jgt.3190030306

[2] R.C. Brigham, J.R. Carrington and R.D. Dutton, Global domination, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer, Cham 2020) 497–519. https://doi.org/http://dx.doi.org/10.1007/978-3-030-51117-3_15

[3] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 6th Ed. (Chapman & Hall/CRC, New York, 2015). https://doi.org/10.1201/b19731

[4] Y.H. Chen, The dominated coloring problem and its application, in: Computational Science and its Applications-ICCSA 2014, Lecture Notes in Comput. Sci. 8584, (Springer, Cham 2014) 132–145. https://doi.org/10.1007/978-3-319-09153-2_10

[5] R. Gera, C. Rasmussen and S. Horton, Dominator colorings and safe clique partitions, Congr. Numer. 181 (2006) 19–32.

[6] I.S. Hamid and M. Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39 (2019) 325–339. https://doi.org/10.7151/dmgt.2089

[7] J.T. Hedetniemi, S.M. Hedetniemi,\ S.T. Hedetniemi, A.A. McRae and D.F. Rall, Total dominator partitions and colorings of graphs (unpublished 18-page manuscript), (2011).

[8] M.A. Henning, Dominator and total dominator colorings in graphs, in: Structures of Domination in Graphs 66 Dev. Math., T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer, Cham 2021) 101–133. https://doi.org/10.1007/978-3-030-58892-2_5

[9] S. Klavžar and M. Tavakoli, Dominated and dominator colorings over (edge) corona and hierarchical products, Appl. Math. Comput. 390 (2021) 125647. https://doi.org/10.1016/j.amc.2020.125647

[10] V.R. Kulli and B. Janakiram, The total global domination number of a graph, Indian J. Pure appl. Math. 27(6) (1996) 537–542.

[11] H.B. Merouane, M. Haddad, M. Chellali and H. Kheddouci, Dominated coloring of graphs, Graphs Combin. 31 (2015) 713–727. https://doi.org/10.1007/s00373-014-1407-3