Game-chromatic number

Game-chromatic number --- игровое хроматическое число.

In 1991 Bodlaender introduced the game-coloring problem on graphs. Let [math]\displaystyle{ G }[/math] be a graph and let [math]\displaystyle{ X = \{1, \ldots, k\} }[/math] be a set of colors. Consider a two-person game on [math]\displaystyle{ G }[/math] as follows: Players 1 and 2 make alternate moves with player 1 moving first. Each move consists of choosing an uncolored vertex and coloring it with a color from [math]\displaystyle{ X }[/math], so that in the subgraph [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math] induced by the colored vertices the adjacent vertices have distinct colors. The game ends when one of the two players can no longer execute a move. Player 1 wins if all the vertices of [math]\displaystyle{ G }[/math] are colored, otherwise player 2 wins. A graph [math]\displaystyle{ G }[/math] is called [math]\displaystyle{ k }[/math]-game-colorable if player 1 has a winning strategy for [math]\displaystyle{ |X| = k }[/math], and the game-chromatic number [math]\displaystyle{ \chi_{g}(G) }[/math] of [math]\displaystyle{ G }[/math] is the least integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-game-colorable.