Game Chromatic Number on Segmented Caterpillars

By Paige Beidelman

Faculty mentor: Professor Jeb Collins

Graph theory is the study of sets vertices connected by known as edges, which are depicted as lines. The graph coloring game is a game played on a graph with two players, Alice and Bob, such that they alternate to properly color a graph, meaning no adjacent vertices are the same color. Alice wins if every vertex is properly colored with n colors, otherwise Bob wins when a vertex cannot be colored using n colors. While strategies for winning this game may seem helpful, more interesting is the least number of colors needed for Alice to have a winning strategy, which is called the game chromatic number. We classified a specific tree graph noted as segmented caterpillar graphs that have vertices of degree 2, 3, and 4, for which the game chromatic number have not yet been explored.