b-coloring Analysis on Tree Graph Families

Abstract

A tree graph is a connected graph and has no circuits. Tree graphs used in this study include: broom graph, centipede graph, and Banana Tree graph. Graph coloring is the process of giving color to graph elements with the rule that neighboring elements must not have the same color, and the number of colors used must be as minimal as possible. b-coloring of a graph G is a coloring of the vertices of G such that each color class has at least one vertex adjacent to all other color classes. The b-chromatic number of a graph G is denoted by φ(G), is the largest integer k such that G has a b-coloring with k colors. The limit of b-coloring of graph G with maximum degree ∆(G) is as follows, χ(G) ≤ φ(G) ≤ ∆(G) + 1.χ(G) is the chromatic number of a graph G where χ(G) is the minimum value of the color required for proper coloring of graph G. While ∆(G) is the maximum degree of the vertices in graph G. This study uses an exploratory research type with an axiomatic deductive method and a pattern detection method. Based on this study, the results of the b-coloring analysis on the tree graph family are known. The results of this study are expected to be used as study material and the development of scientific knowledge related to b-coloring analysis on other graphs.