A dominator coloring of a graph is a proper coloring in which every vertex of dominates every vertex of at least one-color class possibly its own class and each color class is dominated by at least one vertex. The minimum number of colors required for dominator coloring of is called the dominator chromatic number of and is denoted by . In this paper, we have established the relation between dominator chromatic number , chromatic number and domination number . We have investigated results on total graphs of path and cycle with and .
- Dominator coloring is a variant of proper coloring and it has applications in social networking.
- Compared the variants of coloring and domination number for total graph of Paths and Cycles.
- Obtained the two graph classes for total graph of Paths and Cycles.
- Applied the concept of dominator coloring to interconnection networks.
Theory of domination and graph coloring are among the most fascinating problems in graph theory, algorithms and combinatorial optimizations. Both the domains are enriched with wide range of research scope in the field of applied sciences. For comprehensive results of coloring and domination in graphs, we refer [1-17] respectively. The domination theory is concerned with a dominating set which requires the minimum set of vertices such that every vertex of a graph not in the set has a neighbor in it while in the concept of graph coloring, it is required to color the vertices using different colors in such a way that both the end vertices of the edge receive different colors. These problems of graph coloring and domination problems are often in relation. These problems are NP hard problems, and they are explored from the point of approximation algorithms [18-22] and parameterized complexity [23-25].
We consider a Graph as a simple, finite, connected and undirected graph with vertex set and edge set . A function is said to be proper -coloring of a graph if for all , where u and v are adjacent vertices in . The smallest integer n for which admits a proper coloring using n colors is known as the chromatic number . The color class is the group of vertices that share the same color. The set represents the open neighborhood of whereas the set represents the closed neighborhood of . Every vertex in a graph that is either an element of or a neighbor of at least one element of is refereed as a dominating set. The -set is called the dominating set with minimal cardinality and its cardinality is the domination number . If each vertex of the graph dominates every vertex of a certain color class then the coloring is said to be dominator coloring. The minimum cardinality of colors used in the graph for dominator coloring is called the dominator chromatic number denoted by . It is clear that every vertex dominates its respective color class. The total graph of is the graph with the vertex set and two vertices are adjacent whenever they are either adjacent or incident in .
Gera et al.  presented the idea of dominator coloring. Kavitha and David [27-29] determined the dominator chromatic number for several graph families while Arumugam et al.  have thoroughly investigated it. Gera  has also explored dominator coloring of bipartite graphs. Merouane et al.  analyze the dominator chromatic number of different graph families. Vaidya and Shukla  have studied the dominator coloring for degree splitting graphs of various graph families. The dominator coloring of some classes of graphs are obtained by Yangyang Zhou et al. . The dominator coloring of some different graphs is explored by T. Manjula et al. . The dominator coloring of Mycielskian graphs is obtained by A. Mohammed Abid and T. R. Ramesh Rao . The dominator coloring of central and middle graph of some special graphs were investigated by J. Arockia Aruldoss and G. Gurulakshmi . Dominator coloring of regular graphs was derived by T. Manjula and R. Rajeswari .
The existing State of art for Various results on some domination coloring of graphs can be found in [39-41]. Chellali and Volkmann  found relations between the lower domination parameters and the chromatic number of a graph. The concepts of domination and graph coloring are known to be W-complete  and para-NP complete respectively in parameterized complexity. The theory of domination and graph coloring have wide number of applications which led to the algorithmic study of numerous variants of these problems. The algorithmic aspects on dominator coloring of graphs are studied by Arumugam et al. .
The objective to find a dominator coloring for graph G is to minimize the number of color classes. Here we outline a significant use of a dominator coloring problem in the social network. To draw a graph of social network, vertices are denoted as social players while the connection between them is shown as edges that is two players are joined by an edge if they are friends. Two strangers can become friends by their mutual friends. Also, each friend wants to serve as a significant mediator for other strangers in order to help them establish interpersonal relationships inside the social network. The dominator coloring problem involves finding the minimum groups of players in the social network with the following characteristics:
1) Players in the same group are strangers.
2) Players in the same group can become friends by at least one common mutual friend.
3) Each player is an intermediary of at least one stranger group.
In the existing literature, the various results on particular graph families are obtained for dominator colorings of graph. Also, certain characterizations, bounds and its properties are discussed for the larger graphs. By the observation of existing literature review, we have obtained the dominator coloring of path and cycle by means of the graph operation as total graph and also, we have proved our results in context of domination number and chromatic number of respective graphs.
These results are useful in terms of bounds of dominator coloring for total graph of path and cycle which can be measured using domination number and chromatic number of a graph. By using these results, one can solve the problem of social networks, channel assignment and time table problem.
Using the presented results, we can solve the problems of standard graph families by means of various graph operations in context of proper coloring and domination number. The new research directions are open for researchers to solve the open problems of dominator coloring for different graph families using various graph operations.
The theory of domination and Graph coloring have various applications in the field of communication, computer, social, biological, air traffic flow network and airline scheduling .
Proposition 2.1 
Proposition 2.2 
For any graph , if and only if has an odd cycle.
For the cycle ,
3. Main Results
Let be the vertices of path and let be the newly added vertices corresponding to the edges of to obtain . Thus . The graph will have vertices and edges. Let and .
If then is a dominating set of and .
If then is a dominating set of and . Hence .
Further since , it follows that .
Let be the vertices of path and let be the newly added vertices corresponding to the edges of to obtain .
Thus . The graph will have vertices and edges.
The graph , contains an odd cycle. According to Proposition 2.2, .
By giving the vertices proper coloring as , , Thus at least three colors are needed for proper coloring. Hence, .
By Proposition 2.2, as includes an odd cycle. Assign the proper coloring to the vertices as for odd and for even . Thus, minimum four colors are required for proper coloring. Therefore .
We keep using the language and notations from Lemma 3.1.
Case 1: 2, 3, 4, 6
When = 2
The graph , by proposition 2.3, .
When = 3
In this case the vertex is the only one vertex in the -set of graph According to Lemma – 3.1, and by Lemma – 3.2, . Hence, by giving the vertices of the -set a number of colors equal to , we define the optimal coloring for .To the remaining vertices of the graph we give number of colors. We denote the coloring pattern as , , . So every vertex dominates the vertices of at least one color class. A dominator coloring is obtained for the corresponding graphs as a result of this proper coloring. Thus, .
When = 4
In this case the set is the only -sets of graph . According to Lemma – 3.1, and by Lemma – 3.2, . Hence, by giving the vertices of the -set a number of colors equal to , we define the optimal coloring for .To the remaining vertices of the graph we give number of colors. We denote the coloring pattern as , , , , ,f, so every vertex dominates the vertices of at least one color class. A dominator coloring is obtained for the corresponding graphs as a result of this proper coloring. Thus, .
When = 6
In this case the set or are only -sets of graph . According to Lemma – 3.1, and by Lemma – 3.2, . Allocating a number of colors to the vertices of the -set that is equal to in order to determine its optimal coloring. Now we use number of colors to color the remaining vertices.
The coloring pattern can be defined as Here every vertex dominates the vertices of at least one color class. As a result the proper coloring creates a dominator coloring for the relevant graph. Therefore, .
Case 2: ,
Let and . If then be a -set of . If then be a -set of .
We start the coloring process by giving the vertices of the -set a number of colors equal to . For the remaining vertices assign number of colors. All the vertices of at least one-color class are dominated by each vertex. This proper coloring pattern satisfies the condition of dominator coloring. Therefore, .
A dominator coloring of using six colors is shown in Figure – 1
Fig. 1TP6and its dominator coloring
Let be the vertices of cycle and let be the newly added vertices corresponding to the edges of to obtain . Then, and .
Case 1: For
According to Proposition 2.2, as the graph has an odd cycle. To give proper coloring to the nodes . Thus, proper coloring is possible with minimum three colors. Hence, .
Case 2: For
Using Proposition – 2.2, as the graph has an odd cycle. To assign proper coloring to the nodes as . By proper coloring at least 4 colors are required. Therefore, .
We continue with the terminology and notations used in Lemma – 3.5.
Case 1: When
The set is one of the -set of graph . According to Proposition 2.1, and by Lemma – 3.5, . Hence, by giving the vertices of the -set a number of colors equal to . We specify the optimal coloring for . Next, we use no. of colors to color code the remaining vertices. The coloring pattern can be summarized as . This coloring meets the requirement for dominator coloring. Thus, .
Case 2: When
The set in this instance is a member of the -set of graph . Proposition – 2.1 states that and Lemma – 3.5 states that . As a result, by giving the vertices of the -set a no. of colors equal to , we specify the ideal coloring for . The remaining vertices are then given colors using no. of colors are the coloring pattern defined. The dominator coloring requirement is met by this coloring. Therefore, .
Case 3: When
Let and . Then, be a -sets of .
The coloring process is started by allocating the vertices of the -set a no. of colors equal to . Then using no. of colors, we apply the colors to the remaining vertices because each vertex predominates over at least one color class worth of vertices. For the relevant graphs, this proper coloring pattern results in a dominator coloring. As a result, .
A dominator coloring of using five colors is shown in Figure 2.
Fig. 2TC5 and its dominator coloring
4. Concluding Remarks
In graph theory, vertex coloring and theory of domination have many applications in computer and communications network such as cell-phone network, vehicular ad hoc network, wireless sensor network etc. The amalgamation of domination and coloring of graphs called the dominator coloring can be used in the study of interconnections networks. Many research papers are published in the era of dominator coloring in which different authors have discussed about the bounds and the dominator chromatic number of standard graph families whereas in our paper, we have obtained the dominator chromatic number for total graph of path and cycle with the help of chromatic number and domination number. That is the characterization of graphs in two classes as and .
P. Franklin, “The four color problem,” American Journal of Mathematics, Vol. 44, No. 3, p. 225, Jul. 1922, https://doi.org/10.2307/2370527
K. Appel and W. Haken, “Every planar map is four colorable. part i: Discharging,” Illinois Journal of Mathematics, Vol. 21, No. 3, pp. 429–490, Sep. 1977, https://doi.org/10.1215/ijm/1256049011
K. Appel, W. Haken, and J. Koch, “Every planar map is four colorable. part ii: Reducibility,” Illinois Journal of Mathematics, Vol. 21, No. 3, pp. 491–567, Sep. 1977, https://doi.org/10.1215/ijm/1256049012
P. M. Pardalos, T. Mavridou, and J. Xue, Handbook of Combinatorial Optimization. Boston, MA: Springer US, 1998, pp. 1077–1141, https://doi.org/10.1007/978-1-4613-0303-9_16
E. Malaguti and P. Toth, “A survey on vertex coloring problems,” International Transactions in Operational Research, Vol. 17, No. 1, pp. 1–34, Jan. 2010, https://doi.org/10.1111/j.1475-3995.2009.00696.x
O. V. Borodin, “Colorings of plane graphs: A survey,” Discrete Mathematics, Vol. 313, No. 4, pp. 517–539, Feb. 2013, https://doi.org/10.1016/j.disc.2012.11.011
G. Z. Li and R. Simha, “The partition coloring problem and its application to wavelength routing and assignment,” in Proceedings of the First Workshop on Optical Networks, pp. 1–19, 2000.
E. Zhu, F. Jiang, C. Liu, and J. Xu, “Partition independent set and reduction-based approach for partition coloring problem,” IEEE Transactions on Cybernetics, Vol. 52, No. 6, pp. 4960–4969, Jun. 2022, https://doi.org/10.1109/tcyb.2020.3025819
G. Macgillivray and K. Seyffarth, “Domination numbers of planar graphs,” Journal of Graph Theory, Vol. 22, No. 3, pp. 213–229, Jul. 1996, https://doi.org/10.1002/(sici)1097-0118(199607)22:3<213::aid-jgt2>3.0.co;2-p
T. W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs. CRC Press, 2013, https://doi.org/10.1201/9781482246582
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in Graphs. Routledge, 2017, https://doi.org/10.1201/9781315141428
T. Honjo, K.-I. Kawarabayashi, and A. Nakamoto, “Dominating sets in triangulations on surfaces,” Journal of Graph Theory, Vol. 63, No. 1, pp. 17–30, Jan. 2010, https://doi.org/10.1002/jgt.20401
E. L. C. King and M. J. Pelsmajer, “Dominating sets in plane triangulations,” Discrete Mathematics, Vol. 310, No. 17-18, pp. 2221–2230, Sep. 2010, https://doi.org/10.1016/j.disc.2010.03.022
N. Ananchuen, W. Ananchuen, and M. D. Plummer, Domination in Graphs. Boston, MA, USA: Birkhauser, 2011.
C. N. Campos and Y. Wakabayashi, “On dominating sets of maximal outerplanar graphs,” Discrete Applied Mathematics, Vol. 161, No. 3, pp. 330–335, Feb. 2013, https://doi.org/10.1016/j.dam.2012.08.023
Z. Li, E. Zhu, Z. Shao, and J. Xu, “On dominating sets of maximal outerplanar and planar graphs,” Discrete Applied Mathematics, Vol. 198, pp. 164–169, Jan. 2016, https://doi.org/10.1016/j.dam.2015.06.024
C. Liu, “A note on domination number in maximal outerplanar graphs,” Discrete Applied Mathematics, Vol. 293, pp. 90–94, Apr. 2021, https://doi.org/10.1016/j.dam.2021.01.021
U. Feige, “A threshold of ln n for approximating set cover,” Journal of the ACM, Vol. 45, No. 4, pp. 634–652, Jul. 1998, https://doi.org/10.1145/285055.285059
M. M. Halldórsson, “A still better performance guarantee for approximate graph coloring,” Information Processing Letters, Vol. 45, No. 1, pp. 19–23, Jan. 1993, https://doi.org/10.1016/0020-0190(93)90246-6
D. S. Johnson, “Approximation algorithms for combinatorial problems,” Journal of Computer and System Sciences, Vol. 9, No. 3, pp. 256–278, Dec. 1974, https://doi.org/10.1016/s0022-0000(74)80044-9
L. Lovász, “On the ratio of optimal integral and fractional covers,” Discrete Mathematics, Vol. 13, No. 4, pp. 383–390, 1975, https://doi.org/10.1016/0012-365x(75)90058-8
C. Lund and M. Yannakakis, “On the hardness of approximating minimization problems,” Journal of the ACM, Vol. 41, No. 5, pp. 960–981, Sep. 1994, https://doi.org/10.1145/185675.306789
R. G. Downey and M. R. Fellows, Monographs in Computer Science. New York, NY: Springer New York, 1999, https://doi.org/10.1007/978-1-4612-0515-9
J. Flum and M. Grohe., Texts in Theoretical Computer Science. An EATCS Series. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, https://doi.org/10.1007/3-540-29953-x
F. V. Fomin and D. M. Thilikos, “Dominating sets in planar graphs: Branch-width and exponential speed-up,” SIAM Journal on Computing, Vol. 36, No. 2, pp. 281–309, Jan. 2006, https://doi.org/10.1137/s0097539702419649
Craig W. Rasmussen, Ralucca Gera, and S. Horton, “Dominator Colorings and Safe Clique Partitions,” Congressus Numerantium, Vol. 181, pp. 19–32, 2006.
M. Chellali and F. Maffray, “Dominator Colorings in Some Classes of Graphs,” Graphs and Combinatorics, Vol. 28, No. 1, pp. 97–107, Jan. 2012, https://doi.org/10.1007/s00373-010-1012-z
K. Kavitha and N. G. David, “Dominator Coloring on Star and Double Star Graph Families,” International Journal of Computer Applications, Vol. 48, No. 3, pp. 22–25, Jun. 2012, https://doi.org/10.5120/7328-0185
K. Kavitha and N. G. David, “Dominator Coloring of Central Graphs,” International Journal of Computer Applications, Vol. 51, No. 12, pp. 11–14, Aug. 2012, https://doi.org/10.5120/8093-1673
S. Arumugam, J. Bagga, K. Chandrasekar, and Raja, “On dominator coloring in graphs,” Proceedings of the Indian Academy of Sciences (Mathematical Sciences), Vol. 122, No. 4, pp. 561–571, 2012.
R. Gera, “On the Dominator Colorings in Bipartite Graphs,” in 4th International Conference on Information Technology New Generations, pp. 1–6, Apr. 2007, https://doi.org/10.1109/itng.2007.142
H. Merouane, M. Haddad, M. Chellali, and H. Kheddouci, “Dominator colorings of Graphs,” Graphs and Combinatorics, Vol. 31, pp. 713–727, 2014.
R. Kalaivani and D. Vijayalakshmi, “On dominator coloring of degree splitting graph of some graphs.,” Journal of Physics: Conference Series, Vol. 1139, No. 2, p. 012081, Dec. 2018, https://doi.org/10.1088/1742-6596/1139/1/012081
Y. Zhou, D. Zhao, M. Ma, and J. Xu, “Domination Coloring of Graphs,” Mathematics, Vol. 10, No. 6, p. 998, Mar. 2022, https://doi.org/10.3390/math10060998
T. Manjula, R. Rajeswari, A. Dey, and K. Deepika, “Dominator Coloring of Certain Graphs,” International Journal of Engineering and Advanced Technology, Vol. 8, No. 2S, pp. 262–268, 2018.
A. M. Abid and T. R. R. Rao, “Dominator coloring of Mycielskian graphs,” Australas. J Comb., Vol. 73, No. 2, pp. 274–279, 2019.
J. Aruldoss and G. Gurulakshmi, “The Dominator Coloring of Central and Middle Graph of Some Special Graphs,” International Journal of Mathematics and its Applications, Vol. 4, No. 4, pp. 67–73, 2016.
T. Manjula and R. Rajeswari, “Dominator Coloring Number of Regular Graphs,” Advances in Dynamical Systems and Applications, Vol. 16, No. 2, pp. 1427–1440, 2021.
G. Bagan, H. Boumediene-Merouane, M. Haddad, and H. Kheddouci, “On some domination colorings of graphs,” Discrete Applied Mathematics, Vol. 230, pp. 34–50, Oct. 2017, https://doi.org/10.1016/j.dam.2017.06.013
F. Choopani, A. Jafarzadeh, A. Erfanian, and D. A. Mojdeh, “On dominated coloring of graphs and some nordhaus-gaddum-type relations,” Turkish Journal of Mathematics, Vol. 42, No. 5, pp. 2148–2156, Sep. 2018, https://doi.org/10.3906/mat-1710-97
R. Krithika, A. Rai, S. Saurabh, and P. Tale, “Parameterized and exact algorithms for class domination coloring,” Discrete Applied Mathematics, Vol. 291, pp. 286–299, Mar. 2021, https://doi.org/10.1016/j.dam.2020.12.015
M. Chellali and L. Volkmann, “Relations between the lower domination parameters and the chromatic number of a graph,” Discrete Mathematics, Vol. 274, No. 1-3, pp. 1–8, Jan. 2004, https://doi.org/10.1016/s0012-365x(03)00093-1
S. Arumugam, J. Bagga, and K. R. Chandrasekar, “On dominator colorings in graphs,” Proceedings – Mathematical Sciences, Vol. 122, No. 4, pp. 561–571, Nov. 2012, https://doi.org/10.1007/s12044-012-0092-5
S. Arumugam, K. R. Chandrasekar, N. Misra, G. Philip, and S. Saurabh, “Algorithmic Aspects of Dominator Colorings in Graphs,” in Lecture Notes in Computer Science, pp. 19–30, 2011, https://doi.org/10.1007/978-3-642-25011-8_2
M. T., R. R., and P. T. R., “Analytical modeling on the coloring of certain graphs for applications of air traffic and air scheduling management,” Aircraft Engineering and Aerospace Technology, Vol. 94, No. 4, pp. 623–632, Mar. 2022, https://doi.org/10.1108/aeat-04-2021-0104
S. Vaidya and N. Kothari, “Equi independent equitable domination number of cycle and bistar related graphs,” IOSR Journal of Mathematics, Vol. 11, No. 6, pp. 26–32, 2015, https://doi.org/10.9790/5728-11642632
J. Clark and D. Holtan, A First Look at Graph Theory. London: World Scientific Publishing, 1991.
S. Arumugam, J. Bagga, and K. Raja Chandrasekar, “On Dominator Coloring in Graphs,” Proceedings of the Indian Academy of Sciences (Mathematical Sciences), Vol. 122, No. 4, pp. 561–571, 2012.
About this article
The authors have not disclosed any funding.
The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.
The authors declare that they have no conflict of interest.