Article in press
Authors:
Mustapha Chellali
Department of MathematicsUniversity of BlidaB.P. 270, Blida, ALGERIA
email: m_chellali@yahoo.com
Title:
Global dominated coloring of graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-12-06 , Revised: 2023-04-02 , Accepted: 2023-04-04 , Available online: 2023-05-01 , https://doi.org/10.7151/dmgt.2498
Abstract:
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
References:
- 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 - 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 - G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 6th Ed. (Chapman & Hall/CRC, New York, 2015).
https://doi.org/10.1201/b19731 - 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 - R. Gera, C. Rasmussen and S. Horton, Dominator colorings and safe clique partitions, Congr. Numer. 181 (2006) 19–32.
- 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 - 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).
- 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 - 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 - V.R. Kulli and B. Janakiram, The total global domination number of a graph, Indian J. Pure appl. Math. 27(6) (1996) 537–542.
- 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
Close