Graph Coloring Game
The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a Graph (discrete mathematics), graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it. Vertex coloring game The vertex coloring game was introduced in 1981 by Steven Brams as a map-coloring game and rediscovered ten years after by Bodlaender. Its rules are as follows: # Alice and Bob color the vertices of a graph ''G'' with a set ''k'' of colors. # Alice and Bob take turns, graph coloring#Vertex coloring, coloring properly an uncolored vertex (in the standard version, Alice begins). # If a vertex ''v'' is impossible to color properly (for any color, ''v'' has a neighbor colored with it), the ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]