Designing a two-player majority coloring game with a user interface

This thesis examines a Majority Coloring Game in which two players alternately color the vertices of a graph. In this game, one player (Alice) attempts to color the graph in accordance with the majority rule, while the other player (Bob) tries to sabotage this process. The study develops algorithmic strategies such as Greedy, Stackelberg, and OddReduction, and provides a detailed analysis of how structural properties, color constraints, the number and placement of odd-degree vertices, and the competitive interactions between players affect the level of game difficulty. Various graph families, including cycle, wheel, Petersen, and cubical graphs, were experimentally investigated. The effects of graph size, vertex degree distribution, and the number of available colors on game complexity were also evaluated. In addition, an interactive game interface was developed using the Unity game engine, enabling real-time gameplay against an AI opponent (Bob) employing different strategies. This platform serves both as a pedagogical tool for teaching graph theory and the majority coloring approach and as an experimental environment for validating theoretical findings. The results demonstrate that game complexity is significantly influenced by graph topology, the arrangement of odd-degree vertices, color constraints, and competitive dynamics. These findings provide valuable insights into the relationship between strategic decision-making and structural factors.