IJPAM: Volume 120, No. 4 (2018)




V. Praba$^1$, V. Swaminathan$^2$, P. Aristotle$^3$
$^1$Sri Chandrasekharendra Saraswathi Viswa Mahavidyalaya
Kanchipuram, 631 561, Tamilnadu, INDIA
$^1$Department of Mathematics
Rajalakshmi Engineering College
Chennai, 602 105, Tamilnadu, INDIA
$^2$Ramanujan Research Center in Mathematics
Saraswathi Narayanan College
Madurai, 625 022, Tamilnadu, INDIA
$^3$PG & Research Department of Mathematics
Raja Doraisingam Government Arts College
Sivagangai, 630 561, Tamilnadu, INDIA


Let $G=(V, E)$ be a finite, simple and undirected graph. A partition of $V(G)$ into independent sets such that each independent set is dominated by a vertex belonging to $V$ is called a color class domination partition (in short $cd$-partition) [[3], [4], [10], [11], [12]]. The minimum cardinality of a $cd$-partition is called the $cd$-chromatic number of $G$ and is denoted by $\chi_{cd}(G)$. A proper coloring of $G$ in which each vertex of the graph dominates some color class is called a dominator coloring of $G$ and the minimum number of color classes in a dominator coloring of $G$ is called the dominator chromatic number of $G$ and is denoted by $\chi_{d}(G)$ [[1], [5],[6], [8]]. In a $\chi_{d}$-partition of $G$, any set formed by selecting one vertex each from every color class becomes a dominating set of $G$. That is, in such a dominating set each vertex has distinct color and no color is represented by more than one element. Thus, a $\chi_{d}$-coloring gives rise to a dominating set which can be rightly called a colorful dominating set of $G$ (also called gamma coloring of $G$ [8]). In the case of $\chi_{cd}$-partition, this does not happen generally. So, it is a nice problem to find the minimum cardinality of a $cd$-partition which will give rise to a colorful dominating set. This new parameter is denoted by $\chi_{\gamma}^{cd}(G)$. A study of this parameter is initiated in this paper.


Received: June 7, 2017
Revised: September 9, 2017
Published: August 4, 2019

AMS Classification, Key Words

AMS Subject Classification: 05C69
Key Words and Phrases: color class domination partition, dominator chromatic number, colorful dominating set, dominator coloring

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.


S. Arumugam, J. Bagga, K. Raja Chandrasekar, On dominator colorings in graphs, Proc. Indian Acad. Sci. (Math Sci.), Vol. 122, No. 4 (2012), 561-578.

R. Balakrishnan, K. Ranganathan, A textbook of Graph theory, Springer, New York (2nd edition) (2012).

S. Chitra, Studies in Coloring in Graph with Special Reference to Color Class Domination, Ph.D. Thesis, M.K. University (2012).

S. Chitra, Gokilamani, V. Swaminathan, Color Class Domination in Graphs, Mathematical and Experimental Physics, Narosa Publishing House (2010), 24-28.

R. Gera, On Dominator Coloring in Graphs, Graph Theory Notes, New York, 52 (2007), 25-30.

R. Gera, S. Horton, C. Rasmussen, Dominator Colorings and Safe Clique Partitions, Congress Numerantum, 181 (2006), 19-32.

T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc. (1998).

I. Sahul Hamid, R. Gnana Prakasam, Gamma Coloring of Graphs, Communicated.

E. Sampathkumar, C. V. Venkatachalam, Chromatic partition of a graph, Discrete Mathematics, 74 (1989), 227-239.

M. A. Shalu, T. P. Sandhya, The cd-coloring of graphs, Algorithms and Discrete Applied Mathematics, $2^{nd}$ International Conference Caldan (2016), Springer 337-348.

Y. B. Venkatakrishnan, V. Swaminathan, Color class domination number of middle graph and center graph of $K_{1,n}$, $C_n$, $P_n$, Advanced Modeling and Optimization, 12 (2010), 233-237.

Y. B. Venkatakrishnan, V. Swaminathan, Color class domination numbers of some classes of graphs, Algebra and Discrete Mathematics, 18 (2014), 301-305.

How to Cite?

DOI: 10.12732/ijpam.v120i4.12 How to cite this paper?

International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2018
Volume: 120
Issue: 4
Pages: 623 - 638

Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).