Bilangan Kromatik Permainan Graf Ubur-Ubur, Graf Siput, dan Graf Gurita

Abstract

Graph coloring is the process of assigning colors to the vertices or edges of a graph. Specifically, coloring the vertices in graph coloring can be implemented in graph coloring games. This article aims to determine the game chromatic number of the jellyfish graph Jm,n, snail graph SIn, and octopus graph On. For example, give G as a simple, connected, and undirected graph and give two players, namely A as the first player and B as the secondary player. The two players A and B color all the vertices of graph G with available colors. The game’s rules are that A must ensure that all vertices of graph G are colored, while B aims to prevent graph G from being uncolored. Players A and B take turns coloring the vertices of graph G, ensuring that the color of neighboring vertices must be different, with A taking the first turn. If all vertices have been colored, A wins the game, but A loses if some vertices remain uncolored despite available colors, A loses. The smallest value of k for which A has a winning strategy in the game with k colors is the game chromatic number, denoted as χg(G). This thesis discusses the graph coloring game of the tadpole graph Tm,n, broom graph Bn,d, jellyfish graph Jm,n, and tribune graph Tn to find the game chromatic number. The results show that player A uses a strategy to color the vertex with the highest degree in the graph, ensuring that player A always wins. Therefore, the game chromatic number of the jellyfish graph, snail graph, and octopus graph is χg (Jm,n) = 3 for m, n ≥ 1, and χg (SIn) = 3 for n ≥ 1, while χg (On) = 3 for n = 2, 3, 4; χg (On) = 4 for n ≥ 5.