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.

One Reply to “Game Chromatic Number on Segmented Caterpillars”

Comments are closed.