WikiDer > График раскраски

Graph coloring game

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

Вершина раскраски

В вершинная раскраска был представлен в 1981 году Брамсом^[1] и через десять лет заново открыл Бодлендер.^[2] Его правила следующие:

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

В хроматическое число игры графа ${ displaystyle G}$ , обозначаемый ${ displaystyle chi _ {g} (G)}$ , - минимальное количество цветов, необходимое Алисе для победы в игре раскраски вершин на ${ displaystyle G}$ . Тривиально, для каждого графа ${ displaystyle G}$ , у нас есть ${ Displaystyle чи (G) Leq чи _ {g} (G) Leq Delta (G) +1}$ , куда ${ Displaystyle чи (G)}$ это хроматическое число из ${ displaystyle G}$ и ${ Displaystyle Delta (G)}$ его максимум степень.^[3]

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

Ациклическая окраска. Каждый график ${ displaystyle G}$ с ациклическое хроматическое число ${ displaystyle k}$ имеет ${ Displaystyle чи _ {г} (G) Leq К (к + 1)}$ .^[4]

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

Цикл-ограничения на ребрах. Если каждое ребро графа ${ displaystyle G}$ принадлежит самое большее ${ displaystyle c}$ циклы, то ${ displaystyle chi _ {g} (G) leq 4 + c}$ .^[5]

Графические классы

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

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

Декартовы произведения.Игровое хроматическое число декартова произведения ${ displaystyle G square H}$ не ограничена функцией от ${ displaystyle chi _ {g} (G)}$ и ${ displaystyle chi _ {g} (H)}$ . В частности, игровое хроматическое число любого полного двудольного графа ${ displaystyle K_ {n, n}}$ равно 3, но нет верхней границы для ${ Displaystyle чи _ {г} (К_ {п, п} квадрат К_ {м, м})}$ для произвольных ${ displaystyle n, m}$ .^[16]

Для одного ребра имеем:^[16]

{ Displaystyle { begin {align} chi _ {g} (K_ {2} square P_ {k}) & = { begin {cases} 2 & k = 1 3 & k = 2,3 4 & k geq 4 end {case}} chi _ {g} (K_ {2} square C_ {k}) & = 4 && k geq 3 chi _ {g} (K_ {2} square K_ { k}) & = k + 1 end {выровнено}}}

За звезды у нас есть:^[17]

{ Displaystyle { begin {align} chi _ {g} (S_ {m} square P_ {k}) & = { begin {cases} 2 & k = 1 3 & k = 2 4 & k geq 3 end {case}} chi _ {g} (S_ {m} square C_ {k}) & = 4 && k geq 3 end {выровнено}}}

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

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

Эти вопросы все еще открыты до сих пор.

Больше цветов для Алисы ^[18]

Предположим, что у Алисы есть выигрышная стратегия для игры в раскраску вершин на графе. грамм с k цвета. Есть ли у нее один для к + 1 цвета ?
Можно было бы ожидать, что ответ будет «да», так как большее количество цветов кажется Алисе преимуществом. Однако нет никаких доказательств того, что это утверждение верно.
Есть функция ж так что, если у Алисы есть выигрышная стратегия для игры раскраски вершин на графе грамм с k цветов, то у Алисы есть выигрышная стратегия на грамм с f (k) ?
Расслабление предыдущего вопроса.

Отношения с другими понятиями ^[18]

Предположим, что монотонный класс графов (т. Е. Класс графов, замкнутый подграфами) имеет ограниченную хроматическое число игры. Верно ли, что этот класс графов ограничен? игра раскраски номер ?
Предположим, что монотонный класс графов (т. Е. Класс графов, замкнутый подграфами) имеет ограниченные хроматическое число игры. Верно ли, что этот класс графов ограничен? родословие ?
Верно ли, что монотонный класс графов ограниченного хроматическое число игры ограничил ациклическое хроматическое число ?

Снижение максимальной степени ^[7]

Гипотеза: Является ${ displaystyle F}$ это лес, существует ${ Displaystyle F ' substeq F}$ такой, что ${ Displaystyle Дельта (F ') leq chi _ {g} (F)}$ и ${ Displaystyle чи _ {г} (F ') = чи _ {г} (F)}$ .
Позволять ${ Displaystyle { mathcal {G}}}$ - класс графов такой, что для любого ${ Displaystyle G in { mathcal {G}}}$ , Существует ${ Displaystyle G ' substeq G}$ такой, что ${ Displaystyle Дельта (G ') leq chi _ {g} (G)}$ и ${ displaystyle chi _ {g} (G ') = chi _ {g} (G)}$ . Какие семейства графов входят в ${ Displaystyle { mathcal {G}}}$ ?

Гиперкубы^[16]

Это правда, что ${ displaystyle chi _ {g} (G) = n + 1}$ для любого гиперкуба ${ displaystyle Q_ {n}}$ ?
Известно, что это верно для ${ Displaystyle п leq 4}$ .^[16]

Раскраска края

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

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

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

Общий случай

Для каждого графика грамм, ${ Displaystyle чи '(G) Leq чи' _ {g} (G) Leq 2 Delta (G) -1}$ . Есть графы, достигающие этих границ, но все известные нам графы, достигающие этой верхней границы, имеют небольшую максимальную степень.^[19] Существуют графы с ${ displaystyle chi '_ {g} (G)> 1,008 Delta (G)}$ для произвольно больших значений ${ Displaystyle Delta (G)}$ .^[20]

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

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

Графические классы

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

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

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

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

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

Раскраска заболеваемость

В заболеваемость раскраска это игра-раскраска графиков, представленная Андресом,^[24] и похожа на игру раскраски вершин, за исключением того, что Алиса и Боб создают собственное окраска заболеваемости вместо правильной раскраски вершин. Его правила следующие:

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

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

Для каждого графика ${ displaystyle G}$ с максимальной степенью ${ displaystyle Delta}$ , у нас есть ${ displaystyle { frac {3 Delta -1} {2}}$ .^[24]

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

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

Графические классы

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

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

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

Верхняя граница ${ Displaystyle i_ {g} (G) <3 Delta (G) -1}$ плотно для каждого значения ${ Displaystyle Delta (G)}$ ?^[24]
Является ли хроматическое число игры инцидентности монотонным параметром (т. Е. Не меньше ли оно для графа грамм как для любого подграфа грамм) ?^[24]

Примечания

^ Гарднер (1981)
^ Бодлендер (1991)
^ С меньшим количеством цветов, чем хроматическое число, нет правильной окраски грамм и поэтому Алиса не может выиграть. При большем количестве цветов, чем максимальная степень, всегда есть доступный цвет для окраски вершины, поэтому Алиса не может проиграть.
^ Дински и Чжу (1999)
^ Юноша-Сзанявски и Рожей (2010)
^ Faigle et al. (1993), и подразумевается Юноша-Сзанявски и Рожей (2010)
^ ^а ^б Dunn et al. (2014)
^ Сидорович (2007), и подразумевается Юноша-Сзанявски и Рожей (2010)
^ Гуань и Чжу (1999)
^ Верхняя граница Чжу (2008), улучшая предыдущие оценки 33 в Кирстед и Троттер (1994), 30 подразумевается Дински и Чжу (1999), 19 дюйм Чжу (1999) и 18 в Кирстед (2000). Нижняя граница востребована Кирстед и Троттер (1994). См. Обзор игрового хроматического числа плоских графов в Bartnicki et al. (2007).
^ Сэкигуши (2014)
^ He et al. (2002)
^ Распо и Ву (2009)
^ Чжу (2000)
^ Faigle et al. (1993)
^ ^а ^б ^c ^d Петерин (2007)
^ ^а ^б ^c Сиа (2009)
^ ^а ^б Чжу (1999)
^ ^а ^б ^c ^d Лам, Шиу и Сюй (1999)
^ ^а ^б ^c Беверидж и др. (2008)
^ Бартницки и Грычук (2008), улучшая результаты на k-вырожденные графы в Цай и Чжу (2001)
^ Верхняя граница Δ + 2 по Лам, Шиу и Сюй (1999), то оценка Δ + 1 соотношением Erdös et al. (2004) для случаев Δ = 3 и Δ≥6, а по Андрес (2006) для случая Δ = 5.
^ Условия на леса с Δ = 4 приведены в Чан и Нонг (2014)
^ ^а ^б ^c ^d ^е ^ж ^грамм Андрес (2009a)см. также опечатку в Андрес (2009b)
^ ^а ^б Шарпантье и Сопена (2014), расширяя результаты Шарпантье и Сопена (2013).
^ Ким (2011), улучшая аналогичный результат для k ≥ 7 в Андрес (2009a) (см. также опечатку в Андрес (2009b))
^ Ким (2011)

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

Гарднер, Мартин (1981). «Математические игры». Scientific American. Vol. 23.CS1 maint: ref = harv (связь)
Бодлендер, Ханс Л. (1991). «О сложности некоторых раскрасок». Теоретико-графические концепции в компьютерных науках. Конспект лекций по информатике. 484. С. 30–40. CiteSeerX 10.1.1.18.9992. Дои:10.1007/3-540-53832-1_29. ISBN 978-3-540-53832-5.CS1 maint: ref = harv (связь)
Файгл, Ульрих; Керн, Уолтер; Кирстед, Генри А .; Троттер, Уильям Т. (1993). «Об игровом хроматическом числе некоторых классов графов» (PDF). Ars Combinatoria. 35 (17): 143–150.
Кирстед, Генри А .; Троттер, Уильям Т. (1994). «Раскраска плоского графа с партнером, не склонным к сотрудничеству» (PDF). Журнал теории графов. 18 (6): 564–584. Дои:10.1002 / jgt.3190180605.CS1 maint: ref = harv (связь)
Дински, Томас; Чжу, Сюдин (1999). «Оценка хроматического числа графов игры». Дискретная математика. 196 (1–3): 109–115. Дои:10.1016 / s0012-365x (98) 00197-6.CS1 maint: ref = harv (связь)
Guan, D. J .; Чжу, Сюдин (1999). «Игровое хроматическое число внешнепланарных графов». Журнал теории графов. 30 (1): 67–70. Дои:10.1002 / (sici) 1097-0118 (199901) 30: 1 <67 :: aid-jgt7> 3.0.co; 2-m.CS1 maint: ref = harv (связь)
Лам, Питер С. Б.; Shiu, Wai C .; Сюй, Баоган (1999). «Краевая игра раскраска графов» (PDF). Заметки по теории графов Нью-Йорк. 37: 17–19.CS1 maint: ref = harv (связь)
Чжу, Сюдин (1999). «Игра-раскраска чисел плоских графов». Журнал комбинаторной теории, серия B. 75 (2): 245–258. Дои:10.1006 / jctb.1998.1878.CS1 maint: ref = harv (связь)
Кирстед, Генри А. (2000). «Простой конкурентный алгоритм раскраски графов». Журнал комбинаторной теории, серия B. 78 (1): 57–68. Дои:10.1006 / jctb.1999.1927.CS1 maint: ref = harv (связь)
Чжу, Сюдин (2000). "Игра раскраски числа псевдо частичного k-деревья ". Дискретная математика. 215 (1–3): 245–262. Дои:10.1016 / s0012-365x (99) 00237-x.CS1 maint: ref = harv (связь)
Цай, Лейчжэнь; Чжу, Сюдин (2001). "Игровой хроматический указатель k-Вырожденные графики ». Журнал теории графов. 36 (3): 144–155. Дои:10.1002 / 1097-0118 (200103) 36: 3 <144 :: aid-jgt1002> 3.0.co; 2-f.CS1 maint: ref = harv (связь)
Он, Вэньцзе; Хоу, Сяолин; Лих, Ко-Вэй; Шао, Цзятин; Ван, Вэйфань; Чжу, Сюдин (2002). «Реберные разбиения планарных графов и их игровые раскраски чисел». Журнал теории графов. 41 (4): 307–311. Дои:10.1002 / jgt.10069.
Erdös, Peter L .; Файгл, Ульрих; Хохштетлер, Винфрид; Керн, Уолтер (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.CS1 maint: ref = harv (связь)
Бартницки, Томаш; Грычук, Ярослав; Kierstead, H.A .; Чжу, Сюдин (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.CS1 maint: ref = harv (связь)
Сидорович, Эльжбета (2007). «Игровое хроматическое число и игра-раскраска числа кактусов». Письма об обработке информации. 102 (4): 147–151. Дои:10.1016 / j.ipl.2006.12.003.CS1 maint: ref = harv (связь)
Бартницки, Томаш; Грычук, Ярослав (2008). «Заметка об игровом хроматическом указателе графиков». Графы и комбинаторика. 24 (2): 67–70. Дои:10.1007 / s00373-008-0774-z. S2CID 19373685.CS1 maint: ref = harv (связь)
Беверидж, Эндрю; Бохман, Том; Friezeb, Алан; Пихурко, Олег (2008). «Игровой хроматический индекс графов с заданными ограничениями на степени». Теоретическая информатика. 407 (1–3): 242–249. Дои:10.1016 / j.tcs.2008.05.026.CS1 maint: ref = harv (связь)
Чжу, Сюдин (2008). «Доработанная стратегия активации для игры на разметку». Журнал комбинаторной теории, серия B. 98 (1): 1–18. Дои:10.1016 / j.jctb.2007.04.004.CS1 maint: ref = harv (связь)
Андрес, Стефан Д. (2009). «Хроматическое число заболеваемости». Дискретная прикладная математика. 157 (9): 1980–1987. Дои:10.1016 / j.dam.2007.10.021.
Андрес, Стефан Д. (2009). "Исправление к: хроматическому числу заболеваемости в игре". Дискретная прикладная математика. 158 (6): 728. Дои:10.1016 / j.dam.2009.11.017.
Распо, Андре; У, Цзяоцзяо (2009). «Игровое хроматическое число тороидальных сеток». Письма об обработке информации. 109 (21–22): 1183–1186. Дои:10.1016 / j.ipl.2009.08.001.CS1 maint: ref = harv (связь)
Сиа, Чармейн (2009). "Игровое хроматическое число некоторых семейств декартовых графов произведения" (PDF). AKCE Международный журнал графов и комбинаторики. 6 (2): 315–327. Архивировано из оригинал (PDF) на 2011-11-14. Получено 2014-07-16.CS1 maint: ref = harv (связь)
Юноша-Сзанявский, Константин; Рожей, Лукаш (2010). «Игровое хроматическое число графов с локально ограниченным числом циклов». Письма об обработке информации. 110 (17): 757–760. Дои:10.1016 / j.ipl.2010.06.004.CS1 maint: ref = harv (связь)
Ким, Джон Ю. (2011). «Инцидентная игра хроматического числа дорожек и подграфов колес». Дискретная прикладная математика. 159 (8): 683–694. Дои:10.1016 / j.dam.2010.01.001.CS1 maint: ref = harv (связь)
Шарпантье, Клеман; Сопена, Эрик (2013). Игра-раскраска по заболеваемости и древовидность графиков. Конспект лекций по информатике. 8288. С. 106–114. arXiv:1304.0166. Дои:10.1007/978-3-642-45278-9_10. ISBN 978-3-642-45277-2. S2CID 14707501.CS1 maint: ref = harv (связь)
Чан, Вай Х .; Нонг, Ге (2014). «Игровой хроматический индекс некоторых деревьев максимальной степени 4». Дискретная прикладная математика. 170: 1–6. Дои:10.1016 / j.dam.2014.01.003.CS1 maint: ref = harv (связь)
Секигуши, Ёске (2014). «Игра-раскраска числа плоских графов с заданным обхватом». Дискретная математика. 300: 11–16. Дои:10.1016 / j.disc.2014.04.011.CS1 maint: ref = harv (связь)
Шарпантье, Клеман; Сопена, Эрик (2014). "Хроматическое число заболеваемости (объявление)-разложимые графы ». Журнал дискретных алгоритмов. 31: 14–25. Дои:10.1016 / j.jda.2014.10.001.CS1 maint: ref = harv (связь)
Данн, Чарльз; Ларсен, Виктор; Линдке, Кира; Реттер, Трой; Точи, Дастин (2014). «Игра цветного числа деревьев и лесов». arXiv:1410.5223 [math.CO].

[1] Гарднер (1981)

[2] Бодлендер (1991)

[3] С меньшим количеством цветов, чем хроматическое число, нет правильной окраски грамм и поэтому Алиса не может выиграть. При большем количестве цветов, чем максимальная степень, всегда есть доступный цвет для окраски вершины, поэтому Алиса не может проиграть.

[4] Дински и Чжу (1999)

[5] Юноша-Сзанявски и Рожей (2010)

[6] Faigle et al. (1993), и подразумевается Юноша-Сзанявски и Рожей (2010)

[dunn2014-7] а ^б Dunn et al. (2014)

[8] Сидорович (2007), и подразумевается Юноша-Сзанявски и Рожей (2010)

[9] Гуань и Чжу (1999)

[10] Верхняя граница Чжу (2008), улучшая предыдущие оценки 33 в Кирстед и Троттер (1994), 30 подразумевается Дински и Чжу (1999), 19 дюйм Чжу (1999) и 18 в Кирстед (2000). Нижняя граница востребована Кирстед и Троттер (1994). См. Обзор игрового хроматического числа плоских графов в Bartnicki et al. (2007).

[11] Сэкигуши (2014)

[12] He et al. (2002)

[13] Распо и Ву (2009)

[14] Чжу (2000)

[15] Faigle et al. (1993)

[peterin2007-16] а ^б ^c ^d Петерин (2007)

[sia2009-17] а ^б ^c Сиа (2009)

[zhu1999-18] а ^б Чжу (1999)

[lsz1999-19] а ^б ^c ^d Лам, Шиу и Сюй (1999)

[bevetal2008-20] а ^б ^c Беверидж и др. (2008)

[21] Бартницки и Грычук (2008), улучшая результаты на k-вырожденные графы в Цай и Чжу (2001)

[22] Верхняя граница Δ + 2 по Лам, Шиу и Сюй (1999), то оценка Δ + 1 соотношением Erdös et al. (2004) для случаев Δ = 3 и Δ≥6, а по Андрес (2006) для случая Δ = 5.

[23] Условия на леса с Δ = 4 приведены в Чан и Нонг (2014)

[Andres2009-24] а ^б ^c ^d ^е ^ж ^грамм Андрес (2009a)см. также опечатку в Андрес (2009b)

[charpSop2014-25] а ^б Шарпантье и Сопена (2014), расширяя результаты Шарпантье и Сопена (2013).

[26] Ким (2011), улучшая аналогичный результат для k ≥ 7 в Андрес (2009a) (см. также опечатку в Андрес (2009b))

[27] Ким (2011)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

Navigation

Navigation

Themenportale

WikiDer > График раскраски

Содержание

Вершина раскраски

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

Графические классы

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

Раскраска края

Общий случай

Графические классы

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

Раскраска заболеваемость

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

Графические классы

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

Примечания

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