Category Archives: Partizen Graph Coloring

Partizen Graph Coloring

Partizen Graph Coloring Game has two players: Alice and Bob. The players alternate coloring the uncolored vertices of a finite graph G from a fixed finite set of colors. At each step of the game, the players must choose to color an uncolored vertex with a legal color. In the basic formation of the game, a color is legal for an uncolored vertex if the vertex has no neighbors already colored with that color. Alice wins the game if all vertices of the graph are colored; otherwise, Bob wins. The least  such that Alice has a winning strategy for this game on \(G\) is called the game chromatic number of G. If the definition of legal color is altered so that at each step in the game, each color class must have maximum degree at most \(d\), for some fixed integer \(dge{0}\), then the least such that Alice has a winning strategy is called the \(d\)-relaxed game chromatic number of \(G\). These parameters have been studied extensively for many classes of graphs. The classes for which the most is known are trees and forests. While upper bounds on the game chromatic number (and \(d\)-relaxed game chromatic number) are known for these classes, and the bounds are known to be achievable, it is not known what structural properties the graphs must have in order to achieve the bounds. This project will attempt to find these properties, thereby classifying these classes completely with respect to the Partizen Graph Coloring Game. We will then attempt to classify trees and forests relative to the d-relaxed game chromatic number for small values of \(d\). Finally, we may consider other variations of the game in which the definition of legal color is altered in other ways.