Article in press
Authors:
Doost Ali Mojdeh
Department of MathematicsUniversity of MazandaranBabolsar P.O. Box 47416-1467IRAN
email: damojdeh@umz.ac.ir
Title:
Majority dominator colorings of graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-08-09 , Revised: 2024-10-27 , Accepted: 2024-10-27 , Available online: 2024-11-20 , https://doi.org/10.7151/dmgt.2570
Abstract:
Let $G$ be a simple graph of order $n$. A majority dominator coloring of a
graph $G$ is proper coloring in which each vertex of the graph dominates at
least half of one color class. The majority dominator chromatic number
$\chi_{md}(G)$ is the minimum number of color classes in a majority dominator
coloring of $G$. In this paper we study properties of the majority dominator
coloring of a graph. We obtain tight upper and lower bounds in terms of
chromatic number, dominator chromatic number, maximum degree, domination and
independence number. We also study the majority dominator coloring number of
selected families of graphs.
Keywords:
majority dominator chromatic number, majority dominator coloring, chromatic number, independence number, domination number
References:
- A. Abdolghafurian, S. Akbari, S. Hossein Ghorban and S. Qajar, Dominating coloring number of claw-free graphs, Electron. Notes Discrete Math. 45 (2014) 91–97.
https://doi.org/10.1016/j.endm.2013.11.018 - R. Aharoni, E.C. Milner and K. Prikry, Unfriendly partitions of a graph, J. Combin. Theory Ser. B 50 (1990) 1–10.
https://doi.org/10.1016/0095-8956(90)90092-E - M. Anholcer, B. Bosek and J. Grytczuk, Majority choosability of digraphs, Electron. J. Combin. 24 (2017) #P3.57.
https://doi.org/10.37236/6923 - M. Anholcer, B. Bosek and J. Grytczuk, Majority coloring of infinite digraphs, Acta Math. Univ. Comenian. (N.S.) 88(3) (2019) 371–376.
- S. Arumugam, J. Bagga and K.R. Chandrasekar, On dominator colorings in graphs, Proc. Indian Acad. Sci. Math. Sci. 122 (2012) 561–571.
https://doi.org/10.1007/s12044-012-0092-5 - S. Askari, D.A. Mojdeh and E. Nazari, Total global dominator chromatic number of graphs, TWMS J. Appl. and Eng. Math. 12 (2022) 650–661.
- G. Bagan, H. Boumediene-Merouane, M. Haddad and H. Kheddouci, On some domination colorings of graphs, Discrete Appl. Math. 230 (2017) 34–50.
https://doi.org/10.1016/j.dam.2017.06.013 - M. Chellali and F. Maffray, Dominator colorings in some classes of graphs, Graphs Combin. 28 (2012) 97–107.
https://doi.org/10.1007/s00373-010-1012-z - R. Gera, On the dominator colorings in bipartite graphs, in: Fourth International Conference on Information Technology (ITNG'07) (2007) 947–952.
https://doi.org/10.1109/ITNG.2007.142 - R. Gera, On the dominator colorings in graphs, Graph Theory Notes N.Y. 52 (2007) 25–30.
- R. Gera, C. Rasmussen and S. Horton, Dominator colorings and safe clique partition, Congr. Numer. 181 (2006) 19–32.
- R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, 2011).
https://doi.org/10.1201/b10959 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (CRC Press, Boca Raton, 1998).
https://doi.org/10.1201/9781482246582 - M.A. Henning and A. Yeo, Total Domination in Graphs, Springer Monogr. Math. (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - K. Kavitha and N.G. David, Dominator coloring of central graphs, Int. J. Comput. Appl. 51 (2012) 11–14.
https://doi.org/10.5120/8093-1673 - A.P. Kazemi, Total dominator chromatic number of a graph, Trans. Comb. 4(2) (2015) 57–68.
https://doi.org/10.22108/toc.2015.6171 - S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen and D.R. Wood, Majority colourings of digraphs, Electron. J. Combin 24 (2017) #P2.25.
https://doi.org/10.37236/6410 - L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 41 (1966) 237–238.
- H.B. Merouane and M. Chellali, On the dominator coloring in trees, Discuss. Math. Graph Theory 32 (2012) 677–683.
https://doi.org/10.7151/dmgt.1635 - D.A. Mojdeh, S. Askari and E. Nazari, Approach to the central graphs and trees via strong dominator coloring, Ars Combin. to appear.
- T. Ramachandran, D. Udayakumar and A. Naseer Ahmad, Dominator coloring number of some graphs, Int. J. Sci. Res. Publ. 5(10) (2018) 1–4.
http://www.ijsrp.org/research-paper-1015.php?rp=P464625 - S. Shelah and E.C. Milner, Graphs with no unfriendly partitions, in: A Tribute to Paul Erdős, A.Baker, B. Bollobás and A. Hajnal (Ed(s)), (Cambridge Univ. Press, Cambridge 1990) 373–384.
https://doi.org/10.1017/CBO9780511983917.031 - D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, 2001).
- R.J. Wilson, Introduction to Graph Theory, Fourth Edition (Prentice Hall, 1996).
Close