Date of Award
2017
Document Type
Thesis
Degree Name
Bachelor of Science (BS)
Department
Mathematics, Physics and Statistics
Abstract
In 1981 the famous graph coloring game was introduced by Brams. The idea was to play a simple two player game upon any given graph. The players, commonly referred to as Alice and Bob, would take turns coloring the vertices of the graph. They were allowed to choose a color from a given set of k possible colors with Alice making the first move. The major rule to the game was that vertices connected by an edge, known as adjacent vertices, could not be colored with the same color. Alice would win if the entire graph was successfully colored in accordance with the rules of the game. Bob would win if he could keep the graph from being completely colored. Although this game may seem simple, it sparked wide interest among gamers and mathematicians alike. Within the short time period since the conception of the game, numerous versions have been created by people hoping to learn something new from games. These new games have resulted in many new theorems, proofs, and open questions within the realms of game theory, graph theory, and computer science. The goal of this paper is to highlight several of these games and introduce a new game that can be used to understand graphs better. Specifically, the focus of the paper will be on two different types of games that have been connected with graphs and studied recently. The results of these studies will be included in the explanations of these two games, with the intent of helping the reader better understand the design and motivation for the new game addressed at the end of this paper.
Recommended Citation
Weaver, Nicholas, "Graph Coloring Games" (2017). Honors Projects and Presentations: Undergraduate. 11.
https://mosaic.messiah.edu/honors/11