BILANGAN KROMATIK EQUITABLE PADA GRAF BINTANG, GRAF LOLIPOP, DAN GRAF PERSAHABATAN

Abstract

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 (S_n), lollipop graph (L_n), and friendship graph (f_n). This research aims to formulate the equitable chromatic number of the star graph (S_n), lollipop graph (L_n), and friendship graph (f_n). The first step taken in this research is to apply vertex coloring to S_n, L_n, and f_n. 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 S_n is ⌈n/2⌉ + 1, the equitable chromatic number of L_n is n, and the equitable chromatic number of f_n is 3, for n = 1 and n + 1, for n ≥ 2.