Brass Knuckles Graph and its Chromatic Number

Let G = is a graph, the chromatic number in a graph is denoted by χ(G) which is the minimum integer of coloring in a graph G. To determine the chromatic number of a graph, this research uses the method of finding the upper and lower bounds of the graph’s chromatic number. This research aims to introduce a new class of graphs called the Brass Knuckles Graph and determine its chromatic number. Brass Knuckles Graph denoted by BK_m,n is a graph constructed by m duplicates of simple cycle graph C_n namely mC_n with it’s vertices v_{(i, j)} for i = 1, 2,..., m and j = 1, 2,..., n also have condition mn ≡ 0(mod 2). Than add some edges (v_{(i, j}), v_{(i+1,n−(n mod 2)+1− j)}) and (v_{(m, j}), v_{(1,n−(n mod 2)+1− j)}) for every j = 1, 2,..., ⌊n/2⌋ and i = 1, 2,..., m − 1, while for n is odd add another edges (v_{(2i−1,n),v(2i,n)}) for every i= 1,2,..., m/2 . Brass Knuckles Graph constructs a connected graph where every vertex has degree 3 with order and size of Brass Knuckles graph are mn and 3.2 mn. The results of this research show that the chromatic number of any Brass Knuckles graph is 2 for n is even, and 3 for n is odd, the same as the chromatic number of the cycle graph C_n which is a subgraph of the Brass Knuckles graph.