BILANGAN KROMATIK EQUITABLE PADA GRAF BINTANG, GRAF LOLIPOP, DAN GRAF PERSAHABATAN - Yuda Praja; Fransiskus Fran; Nilamsari Kusumastuti (Mathematics Study Program, Faculty of Mathematics and Natural Sciences, Lambung Mangkurat, 2023)
Let G be a connected and undirected graph. Vertex coloring in a graph G is a mapping from the set of vertices in G to the set of colors such that every two adjacent vertices have different colors. There are many types of vertex coloring, such as complete coloring, k-differential coloring, and equitable coloring. Equitable coloring of G is a vertex coloring of G that satisfies the condition that for each induced color class it has an equitable cardinality with difference 0 or 1. The minimum number of colors used for such coloring of G is called the equitable chromatic number of G, denoted by χe(G). In this study, we only concern with graphs that have a central vertex, which means a vertex that is adjacent to every other vertex, in particular on the star graph (Sn), lollipop graph (Ln), and friendship graph (fn). This research aims to formulate the equitable chromatic number of the star graph (Sn), lollipop graph (Ln), and friendship graph (fn). The first step taken in this research is to apply vertex coloring to Sn, Ln, and fn. After that, the color classes of the vertex set are obtained and its cardinality is determined. Next, analyze that the applied vertex coloring meets the definition of equitable coloring. Then, prove that the number of colors used is minimum. Thus, the chromatic number for each graph is obtained and proved. Based on this research, the equitable chromatic number of Sn is ⌈n/2⌉ + 1, the equitable chromatic number of Ln is n, and the equitable chromatic number of fn is 3, for n = 1 and n + 1, for n ≥ 2.