On the dominated chromatic number of certain graphs

Document Type : Research Paper


Department of Mathematics, Yazd University, 89195-741, Yazd, Iran


‎Let $G$ be a simple graph‎. ‎The dominated coloring of $G$ is a proper coloring of $G$ such that each color class is dominated by at least one vertex‎. ‎The minimum number of colors needed for a dominated coloring of $G$ is called the dominated chromatic number of $G$‎, ‎denoted by $\chi_{dom}(G)$‎. ‎Stability (bondage number) of dominated chromatic number of $G$ is the minimum number of vertices (edges) of $G$ whose removal changes the dominated chromatic number of $G$‎. ‎In this paper‎, ‎we study the dominated chromatic number‎, ‎dominated stability and dominated bondage number of certain graphs‎.


Main Subjects

[1] S. Akbari, S. Klavžar, N. Movarraei and M. Nahvi, Nordhaus-Gaddum and other bounds for the chromatic edge-
stability number, European J. Combin., 84 (2020) 8 pp.
[2] S. Alikhani and S. Soltani, Stabilizing the distinguishing number of a graph, Comm. Algebra, 46 (2018) 5460–5468.
[3] D. Bauer, F. Harary, J. Nieminen and C. L. Suffel, Domination alteration sets in graphs, Discrete Math., 47 (1983)
[4] O. V. Borodin, Colorings of plane graphs: A survey, Discrete Math., 313 (2013) 517–539.
[5] F. Choopani, A. Jafarzadeh, A. Erfanian and D. A. Mojdeh, On dominated coloring of graphs and some Nardhaus-
Gaddum-type relations, Turkish J. Math., 42 (2018) 2148–2156.
[6] E. Deutsch and S. Klav̌zar, Computing Hosoya polynomials of graphs from primary subgraphs, MATCH Commun.
Math. Comput. Chem., 70 (2013) 627–644.
[7] C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153–169.
[8] A. P. Kazemi, Total dominator chromatic number of a graph, Trans. Comb., 4 no. 2 (2015) 57–68.
[9] R. Gera, C. Ramussen and S. Horton, Dominator colorings and safe clique partitions, Congr. Numer., 181 (2006)
[10] N. Ghanbari and S. Alikhani, More on the total dominator chromatic number of a graph, J. Inf. Optim. Sci., 40
(2019) 157–169.
[11] N. Ghanbari and S. Alikhani, Total dominator chromatic number of some operations on a graph, Bull. Comput.
Appl. Math., 6 (2018) 9–20.
[12] N. Jafari Rad, Domination in circulant graph, An. tiin. Univ. “Ovidius” Constana Ser. Mat., 17 (2009) 169-176.
[13] H. B. Merouane, M. Haddad, M. Chellali and H. Kheddouci, Dominated coloring of graphs, Graphs Combin., 31
(2015) 713–727.
[14] M. Meszka, R. Nedela and A. Rosa, The chromatic number of 5-valent circulants, Discrete Math., 308 (2008)
[15] F. Ramezani, Coloring problem of signed interval graphs, Trans. Comb., 8 (2019) 1–9.
[16] A. Sadeghieh, N. Ghanbari and S. Alikhani, Computation of Gutman index of some cactus chains, Electron. J.
Graph Theory Appl., 6 (2018) 138–151.
[17] P. Zhang, A Kaleidoscopic View of Graph Colorings, Springer, 2016.
Volume 9, Issue 4 - Serial Number 4
December 2020
Pages 217-230
  • Receive Date: 25 September 2019
  • Revise Date: 02 August 2020
  • Accept Date: 09 August 2020
  • Published Online: 01 December 2020