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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

\chi(G) \leq \chi_{g}(G) \leq |V(G)|,

где \,\chi(G)хроматическое число. Если \,Gплоский граф, то

7 \leq \chi_{g}(G) \leq 33.

Литература

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