Indian Journal of Science and Technology
Year: 2022, Volume: 15, Issue: 20, Pages: 976-982
R Gnanaprakasam1*, I Sahul Hamid2
1Lecturer in Mathematics, Tamilnadu Government Polytechnic College (Autonomous), Madurai11, India
2Assistant professor in Mathematics, The Madura College (Autonomous), Madurai-11, India
Email: [email protected]
Received Date:11 December 2021, Accepted Date:04 February 2022, Published Date:28 May 2022
Background: Given a graph G, the gamma coloring problem seeks for a proper coloring C of G with the property that there exists a dominating set of G in which all the vertices receive different colors under the coloring C. The minimum number of colors required for a gamma coloring of G is called the gamma chromatic number of G and is denoted by cg (G). Our aim is to find the gamma chromatic number of Mycielskian graphs. Methods: Here, we obtain gamma coloring for Mycielskian graph m(G) from a gamma coloring of G by generalizing the give gamma coloring of G. To prove cg (m(G)) m for a graph G, we gave a gamma coloring to m(G) using m colors. To prove cg (m(G)) = m for a graph G, we first proved that cg (m(G)) m and then gave a gamma coloring to m(G) using m colors. Finding: In this paper, we have initiated a study on Gamma coloring for Mycielskian graph m(G) of a given graph G. We have proved that, the gamma chromatic number cg for m(G) is either cg (G) or cg (G)+1 and thus, we classify the class of all connected graphs into two classes namely Class-1 and Class-2 graphs. Graphs G for which cg (m (G)) =cg (G) are of Class-1 and rest of the graphs are of Class-2. Conditions under which a graph G becomes Class-1/ Class-2 have been established. Novelty: One can investigate towards finding a structural characterization of graph G with cg (m (G)) = cg (G) or cg (m (G)) = cg (G)+1. Gamma coloring is a new variation of graph coloring in which the concepts of coloring and domination are linked using the condition that the coloring admits a dominating set in which every vertex receives different colors and, in this paper, we study about the gamma coloring of Mycielskian graph m(G) of a graph G.
Keywords: Coloring; Dominating Set; Colorful Set; Mycielskian Graphs; Gamma Coloring
© 2022 Gnanaprakasam & Hamid. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Published By Indian Society for Education and Environment (iSee)
Subscribe now for latest articles and news.