Analisis b-Coloring pada Graf Hasil Operasi Comb Graf Siklus

Abstract

Graph coloring is a fundamental topic in graph theory. In b-coloring, the coloring is proper and each color class contains at least one vertex, called a b vertex, which is adjacent to at least one vertex in every other color class. For any graph G, the lower bound and upper bound of the b-chromatic number 𝜑(𝐺) are given by 𝜒(𝐺) and ∆(𝐺) + 1, respectively, where 𝜒(𝐺) denotes the chromatic number of G and ∆(𝐺) denotes the maximum degree of G; hence, 𝜒(𝐺) ≤ 𝜑(𝐺) ≤ ∆(𝐺) + 1. This research investigates b-coloring on graphs obtained from the comb operation with cycle graphs. The objective is to determine the b-chromatic number 𝜑(G) of several comb graphs derived from cycle graphs combined with ladder, triangular snake, sun, and prism graphs. An exploratory research approach is employed using pattern recognition and deductive axiomatic methods. The result yield five new theorems characterizing the b-chromatic number of the studied comb graphs under various parameter conditions. these findings enrich the theoretical development of b-coloring and provide references for future research in graph coloring and graph operations.