Indian Journal of Science and Technology

Abstract

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