THE TWO-PLAYER CHROMATIC NUMBER GAME

Introduction
This game is another variation on the concept of a graph and its chromatic number, but you will now play against the computer! If you draw a bunch of circles, called vertices, and if you join some of them with lines, called edges, you get what is called a graph. You are now ready for the game.

First, you must choose the number of colors allowed; then, you can color the vertices alternately with the computer in such a way that two vertices connected by an edge receive different colors. You win the game if you succeed to color the entire graph with the number of colors fixed at the beginning, otherwise the computer wins. It is certainly easy to win by choosing a large number of colors at the beginning, but the goal of the game is for you to devise ingenious methods to find the smallest possible number of colors for which you can always win, regardless of the opponent. This number is called the two-player chromatic number of the graph.

The concept of a graph is very important in mathematics and industries. Imagine, for example, that in a pet shop you buy several fish, that we represent as vertices, and join two of them by an edge, if one fish might eat the other. You want to buy enough aquariums to hold them all without some fish eating others. The clerk is helping you put the fish in the aquariums but is actually trying to force you to buy as many aquariums as possible. This will happen, for example, if the clerk put a big fish in each of the aquariums, and a small fish remains to be placed. The smallest number of aquariums required so that the clerk is unable to force you to buy another one, regardless of his strategy, is the two-player chromatic number of the graph; the number of aquariums corresponding to the fixed number of colors.

Software
Here is how to download the software, together with some technical information.

How to play
Ten pages of six sample graphs are available, presented in increasing levels of difficulty, and drawing tools are also provided for creating new graphs.

To play, you must first choose the maximum number of colors that will be allowed for the game. Next, you can start to color the vertices and the computer will check your coloring and post a message if two vertices connected by an edge receive the same color. If, however, all is correct, the computer will take its turn, trying to force you to use an extra color. You win the game if you succeed to color the entire graph with the number of colors fixed at the beginning, otherwise the computer wins. You will receive appropriate feedback adapted to the level of difficulty.

 INFO: A quick explanation of the game and other commands. DRAW: The mode "VERTICES" will clear the drawing board to draw vertices on a new graph. The mode "EDGES" will let you add the edges on your graph, and you can come back to this mode at any time to add or remove edges on your graph. PLAY: The computer will let you first choose the maximum number of colors that will be allowed for this game. You are then ready to color the graph. UNDO: You can successively undo the last operations performed; for example, while coloring a graph, "UNDO" will successively remove the colors in reverse order. GRAPHS: A set of six sample graphs are available for each of ten pages, presented in incresing levels of difficulty. SAVE: One graph, completed or in progress, can be saved for each sample graph provided. Use the keyboard to type a title. QUIT: Quit the game to return to the main menu.