Число игровое хроматическое

Число игровое хроматическое (Game chromatic number) — Пусть имеются граф [math]\displaystyle{ \,G, }[/math] множество цветов [math]\displaystyle{ \{1,2, \ldots, k\} }[/math] и два игрока [math]\displaystyle{ \,A }[/math] и [math]\displaystyle{ \,B, }[/math] которые делают свои ходы поочередно. Ход состоит в выборе неокрашенной вершины [math]\displaystyle{ v \in V(G) }[/math] и в окрашивании ее в цвет, отличный от цветов уже окрашенных ее соседей из [math]\displaystyle{ \,N_{G}(v). }[/math] Игра заканчивается и [math]\displaystyle{ \,A }[/math] объявляется победителем, если после [math]\displaystyle{ \,|V(G)| }[/math] ходов граф [math]\displaystyle{ \,G }[/math] становится [math]\displaystyle{ \,k }[/math]-раскрашиваемым. Игра заканчивается и [math]\displaystyle{ \,B }[/math] объявляется победителем, если при некотором ходе выбранная вершина не может быть раскрашена одним из цветов [math]\displaystyle{ \{1, 2, \ldots, k\} }[/math]. Игровым хроматическим числом [math]\displaystyle{ \,\chi_{g}(G) }[/math] называется такое наименьшее [math]\displaystyle{ \,k, }[/math] для которого игрок [math]\displaystyle{ \,A }[/math] имеет выигрышную стратегию. Известно, что

[math]\displaystyle{ \chi(G) \leq \chi_{g}(G) \leq |V(G)|, }[/math]

где [math]\displaystyle{ \,\chi(G) }[/math] — хроматическое число. Если [math]\displaystyle{ \,G }[/math] — плоский граф, то

[math]\displaystyle{ 7 \leq \chi_{g}(G) \leq 33. }[/math]

Литература

• Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.