rgroves – Proposal

For my final project I am going to create a game based on graph coloring which I learned about in my discrete math class. At the time I thought it seemed more like a game than a math problem. The objective of the game will be to color in the vertices of a graph such that no adjacent vertices have the same color. The game will consist of a graph and at the bottom of the screen will be a certain number colored squares determined by the chromatic number of the graph (the minimum number of colors necessary to complete the objective). The player will select a color by clicking on the box, and then click on a vertex to color it in. When the two vertices of an edge are different colors, the edge will turn green and when they are the same the edge will turn red. You will know you have completed the level when all the edges are green. The player can then click to move onto the next level.

I’m not sure if I will be able to make the levels automatically generate as I can’t remember if there’s an algorithm for determining the chromatic number and it also may generate levels that are too easy. If I can’t make them automatically generate, I will simply manually design 25 or so levels.

Here is a sketch of what the beginning of a level, a completed level, and an incorrect coloring would look like.