Игра-раскраска графов

Игра «Раскраска графов» — это математическая игра, связанная с теорией графов . Задачи о раскраске возникли как теоретико-игровые версии известных задач о раскраске графов . В игре-раскраске два игрока используют заданный набор цветов для построения раскраски графа , следуя определенным правилам в зависимости от рассматриваемой нами игры. Один игрок пытается успешно завершить раскраску графа, тогда как другой пытается помешать ему в этом.

Игра-раскраска вершин

Игра -раскраска вершин была представлена ​​в 1981 году Брэмсом. и вновь открыт десять лет спустя Бодлендером. Его правила таковы:

1. Алиса и Боб раскрашивают вершины графа G в набор k цветов.
2. Алиса и Боб по очереди раскрашивают неокрашенную вершину (в стандартной версии Алиса начинает).
3. Если вершину v невозможно правильно раскрасить (для любого цвета вершина v имеет соседа, окрашенного в ее цвет), то побеждает Боб.
4. Если граф полностью раскрашен, то выигрывает Алиса.

Игровое хроматическое число графа $G$, обозначенный $\chi _{g}(G)$, — минимальное количество цветов, необходимое Алисе для победы в игре по раскраске вершин на $G$. Тривиально, для каждого графа $G$, у нас есть $\chi (G)\leq \chi _{g}(G)\leq \Delta (G)+1$, где $\chi (G)$ это хроматическое число $G$ и $\Delta (G)$ его максимальная степень .

В статье Бодлендера 1991 г. вычислительная сложность была оставлена ​​как « интересная открытая проблема ».Только в 2020 году было доказано, что игра PSPACE-Complete.

Связь с другими понятиями

Ациклическая окраска. Каждый график $G$ с ациклическим хроматическим числом $k$ имеет $\chi _{g}(G)\leq k(k+1)$.

Маркировочная игра. Для каждого графика $G$, $\chi _{g}(G)\leq col_{g}(G)$, где $col_{g}(G)$ это раскраски игры номер $G$. Почти все известные верхние оценки хроматического числа игровых графов получены из оценок числа раскрасок игры.

Ограничения цикла на ребрах. Если каждое ребро графа $G$ принадлежит максимум $c$ циклы, затем $\chi _{g}(G)\leq 4+c$.

Классы графов

Для класса ${\mathcal {C}}$ графов мы обозначим через $\chi _{g}({\mathcal {C}})$ наименьшее целое число $k$ такой, что каждый график $G$ из ${\mathcal {C}}$ имеет $\chi _{g}(G)\leq k$. Другими словами, $\chi _{g}({\mathcal {C}})$ — точная верхняя оценка игрового хроматического числа графов этого класса. Это значение известно для нескольких стандартных классов графов и ограничено для некоторых других:

• Леса : $\chi _{g}({\mathcal {F}})=4$. Известны простые критерии определения игрового хроматического числа леса без вершины степени 3. Определить игровое хроматическое число лесов с вершинами степени 3 представляется затруднительным даже для лесов с максимальной степенью 3.
• Кактусы : $\chi _{g}({\mathcal {C}})=5$.
• Внепланарные графики : $6\leq \chi _{g}({\mathcal {O}})\leq 7$.
• Планарные графики : $7\leq \chi _{g}({\mathcal {P}})\leq 17$.
• Плоские графики заданного обхвата : $\chi _{g}({\mathcal {P}}_{4})\leq 13$, $\chi _{g}({\mathcal {P}}_{5})\leq 8$, $\chi _{g}({\mathcal {P}}_{6})\leq 6$, $\chi _{g}({\mathcal {P}}_{8})\leq 5$.
• Тороидальные сетки : $\chi _{g}({{\mathcal {T}}G})=5$.
• Частичные k -деревья : $\chi _{g}({\mathcal {T}}_{k})\leq 3k+2$.
• Интервальные графики : $2\omega \leq \chi _{g}({\mathcal {I}})\leq 3\omega -2$, где $\omega$ для графа равен размеру его наибольшей клики .

Декартовы произведения. Игровое хроматическое число декартова произведения $G\square H$ не ограничен функцией $\chi _{g}(G)$ и $\chi _{g}(H)$. В частности, игровое хроматическое число любого полного двудольного графа $K_{n,n}$ равно 3, но верхняя граница для него отсутствует. $\chi _{g}(K_{n,n}\square K_{m,m})$ для произвольного $n,m$. С другой стороны, игровое хроматическое число $G\square H$ ограничено сверху функцией ${\textrm {col}}_{g}(G)$ и ${\textrm {col}}_{g}(H)$. В частности, если ${\textrm {col}}_{g}(G)$ и ${\textrm {col}}_{g}(H)$ оба максимум $t$, затем $\chi _{g}(G\square H)\leq t^{5}-t^{3}+t^{2}$.

• Для одного края имеем:

${\begin{aligned}\chi _{g}(K_{2}\square P_{k})&={\begin{cases}2&k=1\\3&k=2,3\\4&k\geq 4\end{cases}}\\\chi _{g}(K_{2}\square C_{k})&=4&&k\geq 3\\\chi _{g}(K_{2}\square K_{k})&=k+1\end{aligned}}$

• Для звезд у нас есть:

${\begin{aligned}\chi _{g}(S_{m}\square P_{k})&={\begin{cases}2&k=1\\3&k=2\\4&k\geq 3\end{cases}}\\\chi _{g}(S_{m}\square C_{k})&=4&&k\geq 3\end{aligned}}$

• Деревья : $\chi _{g}(T_{1}\square T_{2})\leq 12.$
• Колеса : $\chi _{g}(P_{2}\square W_{n})=5$ если $n\geq 9.$
• Полные двудольные графы : $\chi _{g}(P_{2}\square K_{m,n})=5$ если $m,n\geq 5.$

Открытые проблемы

Эти вопросы остаются открытыми и по сей день.

показывать

Больше цветов для Алисы

• Suppose Alice has a winning strategy for the vertex coloring game on a graph G with k colors. Does she have one for k+1 colors ?
  One would expect the answers to be "yes", as having more colors seems an advantage to Alice. However, no proof exists that this statement is true.
• Is there a function f such that, if Alice has a winning strategy for the vertex coloring game on a graph G with k colors, then Alice has a winning strategy on G with f(k) ?
  Relaxation of the previous question.

показывать

Отношения с другими понятиями

• Suppose a monotone class of graphs (i.e. a class of graphs closed by subgraphs) has bounded game chromatic number. Is it true that this class of graph has bounded game coloring number ?
• Suppose a monotone class of graphs (i.e. a class of graphs closed by subgraphs) has bounded game chromatic number. Is it true that this class of graph has bounded arboricity ?
• Is it true that a monotone class of graphs of bounded game chromatic number has bounded acyclic chromatic number ?

показывать

Снижение максимальной степени

• Conjecture: Is $F$ is a forest, there exists $F'\subseteq F$ such that $\Delta (F')\leq \chi _{g}(F)$ and $\chi _{g}(F')=\chi _{g}(F)$.
• Let ${\mathcal {G}}$ be the class of graphs such that for any $G\in {\mathcal {G}}$, there exists $G'\subseteq G$ such that $\Delta (G')\leq \chi _{g}(G)$ and $\chi _{g}(G')=\chi _{g}(G)$. What families of graphs are in ${\mathcal {G}}$ ?

показывать

Гиперкубы

• Is it true that $\chi _{g}(G)=n+1$ for any hypercube $Q_{n}$ ?
  It is known to be true for $n\leq 4$.

Игра-раскраска края

Игра -раскраска по краям , представленная Ламом, Шиу и Зу. похожа на игру с раскраской вершин, за исключением того, что Алиса и Боб создают правильную раскраску ребер вместо правильной раскраски вершин. Его правила таковы:

1. Алиса и Боб раскрашивают ребра графа G в набор k цветов.
2. Алиса и Боб по очереди правильно раскрашивают неокрашенное ребро (в стандартной версии Алиса начинает).
3. Если ребро e невозможно правильно раскрасить (для любого цвета e соседствует с ребром, окрашенным в него), то выигрывает Боб.
4. Если граф полностью раскрашен по краям, то выигрывает Алиса.

Хотя эту игру можно рассматривать как частный случай игры -раскраски вершин на линейных графах , в научной литературе в основном она рассматривается как отдельная игра. Игровой хроматический показатель графа $G$, обозначенный $\chi '_{g}(G)$, — минимальное количество цветов, необходимое Алисе для победы в этой игре. $G$.

Общий случай

Для каждого G графа $\chi '(G)\leq \chi '_{g}(G)\leq 2\Delta (G)-1$. Существуют графы, достигающие этих границ, но все известные нам графы, достигающие этой верхней границы, имеют небольшую максимальную степень. Существуют графики с $\chi '_{g}(G)>1.008\Delta (G)$ для произвольно больших значений $\Delta (G)$.

Гипотеза. Существует $\epsilon >0$ такая, что для любого произвольного графа $G$, у нас есть $\chi '_{g}(G)\leq (2-\epsilon )\Delta (G)$.
Эта гипотеза верна, когда $\Delta (G)$ достаточно велико по сравнению с количеством вершин в $G$.

• Древовидность. Позволять $a(G)$ быть древесностью графа $G$. Каждый график $G$ с максимальной степенью $\Delta (G)$ имеет $\chi '_{g}(G)\leq \Delta (G)+3a(G)-1$.

Классы графов

Для класса ${\mathcal {C}}$ графов мы обозначим через $\chi '_{g}({\mathcal {C}})$ наименьшее целое число $k$ такой, что каждый график $G$ из ${\mathcal {C}}$ имеет $\chi '_{g}(G)\leq k$. Другими словами, $\chi '_{g}({\mathcal {C}})$ является точной верхней границей игрового хроматического индекса графов этого класса. Это значение известно для нескольких стандартных классов графов и ограничено для некоторых других:

• Колеса : $\chi '_{g}(W_{3})=5$ и $\chi '_{g}(W_{n})=n+1$ когда $n\geq 4$.
• Леса : $\chi '_{g}({\mathcal {F}}_{\Delta })\leq \Delta +1$ когда $\Delta \neq 4$, и $5\leq \chi '_{g}({\mathcal {F}}_{4})\leq 6$.
  Более того, если каждое дерево в лесу $F$ из ${\mathcal {F}}_{4}$ получается подразделением гусеничного дерева или не содержит двух смежных вершин степени 4, то $\chi '_{g}(F)\leq 5$.

Открытые проблемы

Верхняя граница. Есть ли константа $c\geq 2$ такой, что $\chi '_{g}(G)\leq \Delta (G)+c$ для каждого графика $G$ ? Если это правда, то $c=2$ достаточно ?

Гипотеза о больших минимальных степенях. Есть $\epsilon >0$ и целое число $d_{0}$ такой, что любой график $G$ с $\delta (G)\geq d_{0}$ удовлетворяет $\chi '_{g}(G)\geq (1+\epsilon )\delta (G)$.

Игра-раскраска заболеваемости

Игра -раскраска инцидентности — это игра-раскраска графов, предложенная Андресом и похожа на игру с раскраской вершин, за исключением того, что Алиса и Боб создают правильную раскраску инцидентности вместо правильной раскраски вершин. Его правила таковы:

1. Алиса и Боб раскрашивают инцидентности графа G в набор k цветов.
2. Алиса и Боб по очереди правильно раскрашивают неокрашенный объект (в стандартной версии Алиса начинает).
3. Если инцидент i невозможно правильно раскрасить (для любого цвета i соседствует с инцидентом, окрашенным им), то выигрывает Боб.
4. Если все инциденты раскрашены правильно, то Алиса выигрывает.

Хроматическое число игры инцидентности графа $G$, обозначенный $i_{g}(G)$, — минимальное количество цветов, необходимое Алисе для победы в этой игре. $G$.

Для каждого графика $G$ с максимальной степенью $\Delta$, у нас есть ${\frac {3\Delta -1}{2}}<i_{g}(G)<3\Delta -1$.

Отношения с другими понятиями

• (а,г) -Разложение . Это лучшая верхняя оценка, которую мы знаем для общего случая. Если ребра графа $G$ можно разделить на два множества, одно из которых порождает граф с древовидностью $a$, второй порождает граф максимальной степени $d$, затем $i_{g}(G)\leq \left\lfloor {\frac {3\Delta (G)-a}{2}}\right\rfloor +8a+3d-1$.
  Если к тому же $\Delta (G)\geq 5a+6d$, затем $i_{g}(G)\leq \left\lfloor {\frac {3\Delta (G)-a}{2}}\right\rfloor +8a+d-1$.
• Вырождение. Если $G$ является k -вырожденным графом максимальной степени $\Delta (G)$, затем $i_{g}(G)\leq 2\Delta (G)+4k-2$. Более того, $i_{g}(G)\leq 2\Delta (G)+3k-1$ когда $\Delta (G)\geq 5k-1$ и $i_{g}(G)\leq \Delta (G)+8k-2$ когда $\Delta (G)\leq 5k-1$.

Классы графов

Для класса ${\mathcal {C}}$ графов мы обозначим через $i_{g}({\mathcal {C}})$ наименьшее целое число $k$ такой, что каждый график $G$ из ${\mathcal {C}}$ имеет $i_{g}(G)\leq k$.

• Пути : Для $k\geq 13$, $i_{g}(P_{k})=5$.
• Циклы : Для $k\geq 3$, $i_{g}(C_{k})=5$.
• Звезды : Для $k\geq 1$, $i_{g}(S_{2k})=3k$.
• Колеса : Для $k\geq 6$, $i_{g}(W_{2k+1})=3k+2$. Для $k\geq 7$, $i_{g}(W_{2k})=3k$.
• Подграфы Колёс : Для $k\geq 13$, если $G$ является подграфом $W_{k}$ имея $S_{k}$ как подграф, то $i_{g}(G)=\left\lceil {\frac {3k}{2}}\right\rceil$.

Открытые проблемы

• Является ли верхняя граница $i_{g}(G)<3\Delta (G)-1$ плотно для любого значения $\Delta (G)$ ?
• Является ли хроматическое число игры инцидентности монотонным параметром (т. е. является ли оно таким же большим для графа G, как и для любого подграфа G )?

Список литературы (хронологический порядок)

• Гарднер, Мартин (1981). «Математические игры». Научный американец . Том. 23.
• Бодлендер, Ганс Л. (1991). «О сложности некоторых игр-раскрасок». Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 484. стр. 30–40. CiteSeerX   10.1.1.18.9992 . дои : 10.1007/3-540-53832-1_29 . ISBN  978-3-540-53832-5 .
• Фэйгл, Ульрих; Керн, Уолтер; Кирстед, Генри А.; Троттер, Уильям Т. (1993). «Об игре хроматического числа некоторых классов графов» (PDF) . Арс Комбинатория . 35 (17): 143–150.
• Кирстед, Генри А.; Троттер, Уильям Т. (1994). «Раскраска планарного графа с несотрудничающим партнером» (PDF) . Журнал теории графов . 18 (6): 564–584. дои : 10.1002/jgt.3190180605 .
• Дински, Томас; Чжу, Сюйдин (1999). «Оценка хроматического числа графов игры» . Дискретная математика . 196 (1–3): 109–115. дои : 10.1016/s0012-365x(98)00197-6 .
• Гуан, диджей; Чжу, Сюйдин (1999). «Игра хроматического числа внешнепланарных графов». Журнал теории графов . 30 (1): 67–70. doi : 10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m .
• Лам, Питер CB; Шиу, Вай К.; Сюй, Баоган (1999). «Раскраска графов в краевой игре» (PDF) . Заметки по теории графов, Нью-Йорк . 37 : 17–19.
• Чжу, Сюйдин (1999). «Игра-раскраска чисел планарных графов» . Журнал комбинаторной теории, серия B. 75 (2): 245–258. дои : 10.1006/jctb.1998.1878 .
• Кирстед, Генри А. (2000). «Простой конкурентный алгоритм раскраски графа» . Журнал комбинаторной теории, серия B. 78 (1): 57–68. дои : 10.1006/jctb.1999.1927 .
• Чжу, Сюдин (2000). «Игра-раскраска числа псевдочастичных k -деревьев». Дискретная математика . 215 (1–3): 245–262. дои : 10.1016/s0012-365x(99)00237-x .
• Цай, Лэйчжэнь; Чжу, Сюйдин (2001). «Игра Хроматический индекс k -вырожденных графов». Журнал теории графов . 36 (3): 144–155. doi : 10.1002/1097-0118(200103)36:3<144::aid-jgt1002>3.0.co;2-f .
• Он, Вэньцзе; Хоу, Сяолин; Лих, Ко-Вэй; Шао, Цзиатин; Ван, Вэйфан; Чжу, Сюйдин (2002). «Ребро-разбиения планарных графов и их игровые числа раскрасок» . Журнал теории графов . 41 (4): 307–311. дои : 10.1002/jgt.10069 . S2CID   20929383 .
• Эрдеш, Питер Л.; Фэйгл, Ульрих; Хохштеттлер, Винфрид; Керн, Уолтер (2004). «Заметка по игре «Хроматический показатель деревьев» . Теоретическая информатика . 313 (3): 371–376. дои : 10.1016/j.tcs.2002.10.002 .
• Андрес, Стефан Д. (2006). «Игровой хроматический показатель лесов максимальной степени Δ ⩾ 5». Дискретная прикладная математика . 154 (9): 1317–1323. дои : 10.1016/j.dam.2005.05.031 .
• Бартницкий, Томаш; Гричук, Ярослав; Кирстед, штат ХА; Чжу, Сюдин (2007). «Игра-раскраска карт» (PDF) . Американский математический ежемесячник . 114 (9): 793–803. дои : 10.1080/00029890.2007.11920471 . JSTOR   27642332 . S2CID   15901267 .
• Петерин, Изток (2007). «Игра хроматического числа графов декартовых произведений». Электронные заметки по дискретной математике . 29 : 353–357. CiteSeerX   10.1.1.107.111 . дои : 10.1016/j.endm.2007.07.060 .
• Сидорович, Эльжбета (2007). «Игра хроматическое число и игра-раскраска число кактусов» . Письма об обработке информации . 102 (4): 147–151. дои : 10.1016/j.ipl.2006.12.003 .
• Бартницкий, Томаш; Гричук, Ярослав (2008). «Заметка об игровом хроматическом индексе графов». Графы и комбинаторика . 24 (2): 67–70. дои : 10.1007/s00373-008-0774-z . S2CID   19373685 .
• Беверидж, Эндрю; Бохман, Том; Фризеб, Алан; Пихурко, Олег (2008). «Игра хроматического показателя графов с заданными ограничениями на степени». Теоретическая информатика . 407 (1–3): 242–249. дои : 10.1016/j.tcs.2008.05.026 .
• Чжу, Сюйдин (2008). «Усовершенствованная стратегия активации для игры с маркировкой» . Журнал комбинаторной теории, серия B. 98 (1): 1–18. дои : 10.1016/j.jctb.2007.04.004 .
• Андрес, Стефан Д. (2009). «Игра инцидентности хроматического числа» . Дискретная прикладная математика . 157 (9): 1980–1987. дои : 10.1016/j.dam.2007.10.021 .
• Андрес, Стефан Д. (2009). «Ошибка: Хроматическое число игры с инцидентностью» . Дискретная прикладная математика . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
• Распо, Андре; Ву, Цзяоцзяо (2009). «Игра хроматическое число тороидальных сеток». Письма об обработке информации . 109 (21–22): 1183–1186. дои : 10.1016/j.ipl.2009.08.001 .
• Сиа, Чармейн (2009). «Игра хроматического числа некоторых семейств декартовых графов произведений» (PDF) . Международный журнал графов и комбинаторики AKCE . 6 (2): 315–327. Архивировано из оригинала (PDF) 14 ноября 2011 г. Проверено 16 июля 2014 г.
• Юноша-Шанявский, Константин; Рожей, Лукаш (2010). «Игра хроматического числа графов с локально ограниченным числом циклов» . Письма об обработке информации . 110 (17): 757–760. дои : 10.1016/j.ipl.2010.06.004 .
• Ким, Джон Ю. (2011). «Игра инцидентности хроматического числа путей и подграфов колес» . Дискретная прикладная математика . 159 (8): 683–694. дои : 10.1016/j.dam.2010.01.001 .
• Шарпантье, Клеман; Сопена, Эрик (2013). «Игра-раскраска заболеваемости и древесность графов». Комбинаторные алгоритмы . Конспекты лекций по информатике. Том. 8288. стр. 106–114. arXiv : 1304.0166 . дои : 10.1007/978-3-642-45278-9_10 . ISBN  978-3-642-45277-2 . S2CID   14707501 .
• Чан, Вай Х.; Нонг, Ге (2014). «Игровой хроматический показатель некоторых деревьев максимальной степени 4» . Дискретная прикладная математика . 170 : 1–6. дои : 10.1016/j.dam.2014.01.003 .
• Сэкигуши, Ёске (2014). «Игра-раскраска числа плоских графов заданного обхвата». Дискретная математика . 300 : 11–16. дои : 10.1016/j.disc.2014.04.011 .
• Шарпантье, Клеман; Сопена, Эрик (2014). «Хроматическое число игры инцидентности (a, d) -разложимых графов». Журнал дискретных алгоритмов . 31 : 14–25. дои : 10.1016/j.jda.2014.10.001 . S2CID   1102795 .
• Данн, Чарльз; Ларсен, Виктор; Линдке, Кира; Реттер, Трой; Точи, Дастин (2014). «Игра хроматическое число деревьев и лесов». arXiv : 1410.5223 [ math.CO ].
• Коста, Эуринардо; Пессоа, Виктор Лаге; Соарес, Ронан; Сампайо, Рудини (2020). «PSPACE-полнота двух игр-раскрасок графов» . Теоретическая информатика . 824–825: 36–45. дои : 10.1016/j.tcs.2020.03.022 . S2CID   218777459 .
• Брэдшоу, Питер (2021). «Раскраски графов с ограниченными двухцветными подграфами: II. Игра в раскраску графов». Журнал теории графов . 100 (2): 371–383. arXiv : 2008.13275 . дои : 10.1002/jgt.22786 . S2CID   221377336 .