Our intent was to work with young women (although we included some young men in the research as well) on research problems that are quickly understood but not so quickly solved. There were many open problems in graph theory that suited our purposes. Since all of our students understood the moves allowed in the game of chess, we found it easy to interest them in doing graph coloring on chessboard graphs.

In a chessboard graph, each vertex represents one square on the board. The legal moves that a chess piece can make determine the adjacencies between vertices, so each chess piece induces a different chessboard graph. In a Bishops graph, for example, a vertex is adjacent to all the other vertices in its two diagonals.

Graph coloring is a popular research topic in graph theory. In a proper coloring, vertices in a graph are colored such that no two adjacent vertices are assigned the same color. The chromatic number of a graph is the fewest number of colors that can be used in a proper coloring of the graph. The chromatic numbers of most of the square chessboard graphs were known and we began by reviewing those results.

There is another kind of graph coloring (called Grundy coloring) in which we try to force the number of colors to get as high as possible but with a certain requirement. A vertex colored with color k (we use numbers to represent colors) MUST be colored that color because it is adjacent to vertices already colored with all the colors from 1 to k-1. The Grundy number of a graph is the highest number of colors used in a proper Grundy coloring of the graph. No results for Grundy colorings of chessboard graphs were known. We decided to find the Grundy numbers for all the chessboard graphs, both square and rectangular.

We obtained Grundy numbers for several of the chessboard graphs (square and rectangular) and have conjectures for the others. We are currently working on a journal article containing our results and will post the PowerPoint presentations given by our students on the web page shown below.

http://www.cs.appstate.edu/~dap/crew