Английская Википедия:Graph coloring game

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

Vertex coloring game

The vertex coloring game was introduced in 1981 by Brams^[1] and rediscovered ten years after by Bodlaender.^[2] Its rules are as follows:

Alice and Bob color the vertices of a graph G with a set k of colors.
Alice and Bob take turns, coloring properly an uncolored vertex (in the standard version, Alice begins).
If a vertex v is impossible to color properly (for any color, v has a neighbor colored with it), then Bob wins.
If the graph is completely colored, then Alice wins.

The game chromatic number of a graph <math>G</math>, denoted by <math>\chi_g(G)</math>, is the minimum number of colors needed for Alice to win the vertex coloring game on <math>G</math>. Trivially, for every graph <math>G</math>, we have <math>\chi(G) \le \chi_g(G) \le \Delta(G) + 1</math>, where <math>\chi(G)</math> is the chromatic number of <math>G</math> and <math>\Delta(G)</math> its maximum degree.^[3]

In the 1991 Bodlaender's paper,^[4] the computational complexity was left as "an interesting open problem". Only in 2020 it was proved that the game is PSPACE-Complete.^[5]

Relation with other notions

Acyclic coloring. Every graph <math>G</math> with acyclic chromatic number <math>k</math> has <math>\chi_g(G) \le k(k+1)</math>.^[6]

Marking game. For every graph <math>G</math>, <math>\chi_g(G) \le col_g(G)</math>, where <math>col_g(G)</math> is the game coloring number of <math>G</math>. Almost every known upper bound for the game chromatic number of graphs are obtained from bounds on the game coloring number.

Cycle-restrictions on edges. If every edge of a graph <math>G</math> belongs to at most <math>c</math> cycles, then <math>\chi_g(G) \le 4+c</math>.^[7]

Graph Classes

For a class <math>{\mathcal C}</math> of graphs, we denote by <math>\chi_g({\mathcal C})</math> the smallest integer <math>k</math> such that every graph <math>G</math> of <math>{\mathcal C}</math> has <math>\chi_g(G) \le k</math>. In other words, <math>\chi_g({\mathcal C})</math> is the exact upper bound for the game chromatic number of graphs in this class. This value is known for several standard graph classes, and bounded for some others:

Forests: <math>\chi_g({\mathcal F}) = 4</math>.^[8] Simple criteria are known to determine the game chromatic number of a forest without vertex of degree 3.^[9] It seems difficult to determine the game chromatic number of forests with vertices of degree 3, even for forests with maximum degree 3.
Cactuses: <math>\chi_g({\mathcal C}) = 5</math>.^[10]
Outerplanar graphs: <math>6 \le \chi_g({\mathcal O}) \le 7</math>.^[11]
Planar graphs: <math>7 \le \chi_g({\mathcal P}) \le 17</math>.^[12]
Planar graphs of given girth: <math>\chi_g({\mathcal P}_4) \le 13</math>,^[13] <math>\chi_g({\mathcal P}_5) \le 8</math>, <math>\chi_g({\mathcal P}_6) \le 6</math>, <math>\chi_g({\mathcal P}_8) \le 5</math>.^[14]
Toroidal grids: <math>\chi_g({\mathcal TG}) = 5</math>.^[15]
Partial k-trees: <math>\chi_g({\mathcal T}_k) \le 3k+2</math>.^[16]
Interval graphs: <math>2\omega \le \chi_g({\mathcal I}) \le 3\omega-2</math>, where <math>\omega</math> is for a graph the size of its largest clique.^[17]

Cartesian products. The game chromatic number of the cartesian product <math>G \square H</math> is not bounded by a function of <math>\chi_g(G)</math> and <math>\chi_g(H)</math>. In particular, the game chromatic number of any complete bipartite graph <math>K_{n,n}</math> is equal to 3, but there is no upper bound for <math>\chi_g(K_{n,n} \square K_{m,m})</math> for arbitrary <math>n, m</math>.^[18] On the other hand, the game chromatic number of <math>G \square H</math> is bounded above by a function of <math>\textrm{col}_g(G)</math> and <math>\textrm{col}_g(H)</math>. In particular, if <math>\textrm{col}_g(G)</math> and <math>\textrm{col}_g(H)</math> are both at most <math>t</math>, then <math>\chi_g(G \square H) \le t^5 - t^3 + t^2</math>.^[19]

For a single edge we have:^[18]

<math>\begin{align}

\chi_g(K_2 \square P_k) &= \begin{cases} 2 & k = 1 \\ 3 & k=2,3 \\ 4 & k \ge 4 \end{cases} \\ \chi_g(K_2 \square C_k) &= 4 && k \ge 3 \\ \chi_g(K_2 \square K_k) &= k+1 \end{align}</math>

For stars we have:^[20]

<math>\begin{align}

\chi_g(S_m \square P_k) &= \begin{cases} 2 & k = 1 \\ 3 & k=2 \\ 4 & k \ge 3 \end{cases} \\ \chi_g(S_m \square C_k) &= 4 && k \ge 3 \end{align}</math>

Trees: <math>\chi_g(T_1 \square T_2) \le 12.</math>
Wheels: <math>\chi_g(P_2 \square W_n) = 5</math> if <math>n \ge 9.</math>^[20]
Complete bipartite graphs: <math>\chi_g(P_2 \square K_{m,n}) = 5</math> if <math>m, n \ge 5.</math>^[20]

Open problems

These questions are still open to this date.

Шаблон:Hidden Шаблон:Hidden Шаблон:Hidden Шаблон:Hidden

Edge coloring game

The edge coloring game, introduced by Lam, Shiu and Zu,^[21] is similar to the vertex coloring game, except Alice and Bob construct a proper edge coloring instead of a proper vertex coloring. Its rules are as follows:

Alice and Bob are coloring the edges a graph G with a set k of colors.
Alice and Bob are taking turns, coloring properly an uncolored edge (in the standard version, Alice begins).
If an edge e is impossible to color properly (for any color, e is adjacent to an edge colored with it), then Bob wins.
If the graph is completely edge-colored, then Alice wins.

Although this game can be considered as a particular case of the vertex coloring game on line graphs, it is mainly considered in the scientific literature as a distinct game. The game chromatic index of a graph <math>G</math>, denoted by <math>\chi'_g(G)</math>, is the minimum number of colors needed for Alice to win this game on <math>G</math>.

General case

For every graph G, <math>\chi'(G) \le \chi'_g(G) \le 2\Delta(G) -1</math>. There are graphs reaching these bounds but all the graphs we know reaching this upper bound have small maximum degree.^[21] There exists graphs with <math>\chi'_g(G) > 1.008\Delta(G)</math> for arbitrary large values of <math>\Delta(G)</math>.^[22]

Conjecture. There is an <math>\epsilon > 0</math> such that, for any arbitrary graph <math>G</math>, we have <math>\chi'_g(G) \le (2-\epsilon)\Delta(G)</math>.
This conjecture is true when <math>\Delta(G)</math> is large enough compared to the number of vertices in <math>G</math>.^[22]

Arboricity. Let <math>a(G)</math> be the arboricity of a graph <math>G</math>. Every graph <math>G</math> with maximum degree <math>\Delta(G)</math> has <math>\chi'_g(G) \le \Delta(G) + 3a(G) - 1</math>.^[23]

Graph Classes

For a class <math>{\mathcal C}</math> of graphs, we denote by <math>\chi'_g({\mathcal C})</math> the smallest integer <math>k</math> such that every graph <math>G</math> of <math>{\mathcal C}</math> has <math>\chi'_g(G) \le k</math>. In other words, <math>\chi'_g({\mathcal C})</math> is the exact upper bound for the game chromatic index of graphs in this class. This value is known for several standard graph classes, and bounded for some others:

Wheels: <math>\chi'_g(W_3) = 5</math> and <math>\chi'_g(W_n) = n+1</math> when <math>n\ge4</math>.^[21]
Forests : <math>\chi'_g({\mathcal F}_\Delta) \le \Delta + 1 </math> when <math>\Delta \ne 4</math>, and <math>5 \le \chi'_g({\mathcal F}_4) \le 6</math>.^[24]
Moreover, if every tree of a forest <math>F</math> of <math>{\mathcal F}_4</math> is obtained by subdivision from a caterpillar tree or contains no two adjacent vertices with degree 4, then <math>\chi'_g(F) \le 5</math>.^[25]

Open Problems

Upper bound. Is there a constant <math>c \ge 2</math> such that <math>\chi'_g(G) \le \Delta(G) + c</math> for each graph <math>G</math> ? If it is true, is <math>c = 2</math> enough ?^[21]

Conjecture on large minimum degrees. There are a <math>\epsilon > 0</math> and an integer <math>d_0</math> such that any graph <math>G</math> with <math>\delta(G) \ge d_0</math> satisfies <math>\chi'_g(G) \ge (1+\epsilon)\delta(G)</math>. ^[22]

Incidence coloring game

The incidence coloring game is a graph coloring game, introduced by Andres,^[26] and similar to the vertex coloring game, except Alice and Bob construct a proper incidence coloring instead of a proper vertex coloring. Its rules are as follows:

Alice and Bob are coloring the incidences of a graph G with a set k of colors.
Alice and Bob are taking turns, coloring properly an uncolored incidence (in the standard version, Alice begins).
If an incidence i is impossible to color properly (for any color, i is adjacent to an incident colored with it), then Bob wins.
If all the incidences are properly colored, then Alice wins.

The incidence game chromatic number of a graph <math>G</math>, denoted by <math>i_g(G)</math>, is the minimum number of colors needed for Alice to win this game on <math>G</math>.

For every graph <math>G</math> with maximum degree <math>\Delta</math>, we have <math>\frac{3\Delta - 1}{2} < i_g(G) < 3\Delta - 1</math>.^[26]

Relations with other notions

(a,d)-Decomposition. This is the best upper bound we know for the general case. If the edges of a graph <math>G</math> can be partitioned into two sets, one of them inducing a graph with arboricity <math>a</math>, the second inducing a graph with maximum degree <math>d</math>, then <math>i_g(G) \le \left\lfloor \frac{3\Delta(G) - a}{2} \right\rfloor + 8a + 3d - 1</math>.^[27]
If moreover <math>\Delta(G) \ge 5a + 6d</math>, then <math>i_g(G) \le \left\lfloor \frac{3\Delta(G) - a}{2} \right\rfloor + 8a + d - 1</math>.^[27]
Degeneracy. If <math>G</math> is a k-degenerated graph with maximum degree <math>\Delta(G)</math>, then <math>i_g(G) \le 2\Delta(G) + 4k - 2</math>. Moreover, <math>i_g(G) \le 2\Delta(G) + 3k - 1</math> when <math>\Delta(G) \ge 5k - 1</math> and <math>i_g(G) \le \Delta(G) + 8k - 2</math> when <math>\Delta(G) \le 5k -1</math>.^[26]

Graph Classes

For a class <math>{\mathcal C}</math> of graphs, we denote by <math>i_g({\mathcal C})</math> the smallest integer <math>k</math> such that every graph <math>G</math> of <math>{\mathcal C}</math> has <math>i_g(G) \le k</math>.

Paths : For <math>k \ge 13</math>, <math>i_g(P_k) = 5</math>.
Cycles : For <math>k \ge 3</math>, <math>i_g(C_k) = 5</math>.^[28]
Stars : For <math>k \ge 1</math>, <math>i_g(S_{2k}) = 3k</math>.^[26]
Wheels : For <math>k \ge 6</math>, <math>i_g(W_{2k+1}) = 3k + 2</math>. For <math>k \ge 7</math>, <math>i_g(W_{2k}) = 3k</math>.^[26]
Subgraphs of Wheels : For <math>k \ge 13</math>, if <math>G</math> is a subgraph of <math>W_k</math> having <math>S_k</math> as a subgraph, then <math>i_g(G) = \left\lceil \frac{3k}{2} \right\rceil</math>.^[29]

Open Problems

Is the upper bound <math>i_g(G) < 3\Delta(G) - 1</math> tight for every value of <math>\Delta(G)</math> ?^[26]
Is the incidence game chromatic number a monotonic parameter (i.e. is it as least as big for a graph G as for any subgraph of G) ?^[26]

Notes

Шаблон:Reflist

References (chronological order)

Шаблон:Refbegin

Шаблон:Refend

↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ With less colors than the chromatic number, there is no proper coloring of G and so Alice cannot win. With more colors than the maximum degree, there is always an available color for coloring a vertex and so Alice cannot lose.
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt, and implied by Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt, and implied by Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Upper bound by Шаблон:Harvtxt, improving previous bounds of 33 in Шаблон:Harvtxt, 30 implied by Шаблон:Harvtxt, 19 in Шаблон:Harvtxt and 18 in Шаблон:Harvtxt. Lower bound claimed by Шаблон:Harvtxt. See a survey dedicated to the game chromatic number of planar graphs in Шаблон:Harvtxt.
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ ^18,0 ^18,1 Шаблон:Harvtxt
↑ Шаблон:Harvtxt
↑ ^20,0 ^20,1 ^20,2 Шаблон:Harvtxt
↑ ^21,0 ^21,1 ^21,2 ^21,3 Шаблон:Harvtxt
↑ ^22,0 ^22,1 ^22,2 Шаблон:Harvtxt
↑ Шаблон:Harvtxt, improving results on k-degenerate graphs in Шаблон:Harvtxt
↑ Upper bound of Δ+2 by Шаблон:Harvtxt, then bound of Δ+1 by Шаблон:Harvtxt for cases Δ=3 and Δ≥6, and by Шаблон:Harvtxt for case Δ=5.
↑ Conditions on forests with Δ=4 are in Шаблон:Harvtxt
↑ ^26,0 ^26,1 ^26,2 ^26,3 ^26,4 ^26,5 ^26,6 Шаблон:Harvtxt, see also erratum in Шаблон:Harvtxt
↑ ^27,0 ^27,1 Шаблон:Harvtxt, extending results of Шаблон:Harvtxt.
↑ Шаблон:Harvtxt, improving a similar result for k ≥ 7 in Шаблон:Harvtxt (see also erratum in Шаблон:Harvtxt)
↑ Шаблон:Harvtxt

[1] Шаблон:Harvtxt

[2] Шаблон:Harvtxt

[3] With less colors than the chromatic number, there is no proper coloring of G and so Alice cannot win. With more colors than the maximum degree, there is always an available color for coloring a vertex and so Alice cannot lose.

[4] Шаблон:Harvtxt

[5] Шаблон:Harvtxt

[6] Шаблон:Harvtxt

[7] Шаблон:Harvtxt

[8] Шаблон:Harvtxt, and implied by Шаблон:Harvtxt

[dunn2014-9] Шаблон:Harvtxt

[10] Шаблон:Harvtxt, and implied by Шаблон:Harvtxt

[11] Шаблон:Harvtxt

[12] Upper bound by Шаблон:Harvtxt, improving previous bounds of 33 in Шаблон:Harvtxt, 30 implied by Шаблон:Harvtxt, 19 in Шаблон:Harvtxt and 18 in Шаблон:Harvtxt. Lower bound claimed by Шаблон:Harvtxt. See a survey dedicated to the game chromatic number of planar graphs in Шаблон:Harvtxt.

[13] Шаблон:Harvtxt

[14] Шаблон:Harvtxt

[15] Шаблон:Harvtxt

[16] Шаблон:Harvtxt

[17] Шаблон:Harvtxt

[peterin2007-18] 18,0 ^18,1 Шаблон:Harvtxt

[bradshaw2021-19] Шаблон:Harvtxt

[sia2009-20] 20,0 ^20,1 ^20,2 Шаблон:Harvtxt

[lsz1999-21] 21,0 ^21,1 ^21,2 ^21,3 Шаблон:Harvtxt

[bevetal2008-22] 22,0 ^22,1 ^22,2 Шаблон:Harvtxt

[23] Шаблон:Harvtxt, improving results on k-degenerate graphs in Шаблон:Harvtxt

[24] Upper bound of Δ+2 by Шаблон:Harvtxt, then bound of Δ+1 by Шаблон:Harvtxt for cases Δ=3 and Δ≥6, and by Шаблон:Harvtxt for case Δ=5.

[25] Conditions on forests with Δ=4 are in Шаблон:Harvtxt

[Andres2009-26] 26,0 ^26,1 ^26,2 ^26,3 ^26,4 ^26,5 ^26,6 Шаблон:Harvtxt, see also erratum in Шаблон:Harvtxt

[charpSop2014-27] 27,0 ^27,1 Шаблон:Harvtxt, extending results of Шаблон:Harvtxt.

[28] Шаблон:Harvtxt, improving a similar result for k ≥ 7 in Шаблон:Harvtxt (see also erratum in Шаблон:Harvtxt)

[29] Шаблон:Harvtxt

[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]

[28]

[29]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Graph coloring game

Содержание

Vertex coloring game

Relation with other notions

Graph Classes

Open problems

Edge coloring game

General case

Graph Classes

Open Problems

Incidence coloring game

Relations with other notions

Graph Classes

Open Problems

Notes

References (chronological order)

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты