THE CHROMATIC NUMBER OF A GRAPH

Introduction
This game deals with the general concept of a graph and its chromatic number. If you draw a bunch of circles, which we call vertices, and join some of them by lines, which we call edges, you get what is called a graph. If you now color the vertices in such a way that those joined by an edge receive different colors, then the smallest number of colors that can be used is called the chromatic number of the graph. The goal of this game is for you to devise ingenious methods to get as close as possible to this number.

The concept of a graph is very important in mathematics and industries. Think of an airline company tracing routes; cities are thought of as vertices and routes as edges. Or think of computers as vertices and edges being the direct internet connections between them. As another example, suppose you have several fish, thought of as vertices, and join two by an edge if the two fish have a chance to eat each other; then we get a graph and the smallest number of aquariums needed to hold these fish without any danger of two fish eating each other is nothing else but the chromatic number of the graph, the number of aquariums corresponding to the number of colors used, right?

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.

The computer will check the graph after each coloring and will display a message if the same color was used for two connected vertices. The computer also verifies if the graph is completed and counts the number of colors used. Finally, there is a simple algorithm used by the computer to check if it can do better, giving appropriate feedback adapted to the difficulty level.

 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. PAINT: In the mode "COLORS", ten colors are available to color the vertices; they are selected by clicking the can of your choice. The mode "CLEAR" will remove all colors of the graph. UNDO: You can successively undo the last operations performed; for example, while coloring a graph, "UNDO" will remove the colors one by one 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.