Modular Coloring of Comb Graph, Lintang Graph, and Butterfly Graph

Abstract

Given any graph G that contains no isolated vertices, a labeling c is a mapping from its vertex set to the set of integers modulo k (c:V(G)→Z_k) for k≥2, adjacent vertices are allowed to share the same color. The number of color labels of a vertex v (σ(v)), is the number of color labels of the neighborhood of vertex v (N(v)). A labeling c is a modular k-coloring of G if σ(x) ≠ σ(y) in Z_k for all vertices x,y that are neighbors in G. Denoted as mc(G), the modular chromatic number of G is defined as the least integer k that allows for a modular k-coloring of the graph. This research seeks to ascertain the modular chromatic number of the comb graph Cb_n, the lintang graph L_n, and the butterfly graph BF(n). The first step in this research is to define the labeling c, then determine (N(v)). Next, determine the number of color labels from the neighborhood at each vertex with σ(x)≠σ(y) in Z_k for x,y being all neighboring vertices. After the condition σ(x)≠σ(y) in Z_k is satisfied, ascertain mc(G). By performing the same steps on each graph with increasingly larger values of n, a modular coloring pattern will emerge, which is used to formulate the modular coloring formula. This process concludes with the formulation of a modular coloring formula and the determination of the modular chromatic number for comb graph Cb_n, lintang graph L_n, and butterfly graph BF(n). Based on this research, mc(Cb_n)=2, mc(L_n)=2, and mc(BF(n))=3 are obtained.