Сложность раскраски графиков

Предположим, что граф с раскрасочным числом . Рассмотрим следующую игру между Алисой и Бобом. В каждом раунде Алиса выбирает вершину, и Боб отвечает цветом для этой вершины. Игра заканчивается, когда монохроматический край обнаружен. Пусть будет максимальной продолжительностью игры при оптимальной игре обоих игроков (Алиса хочет максимально сократить игру, Боб хочет отложить ее, насколько это возможно). Например, и . $G$ $d = \chi(G)$ $\{1,\ldots,d-1\}$ $X(G)$ $X(K_n) = n$ $X(C_{2n+1}) = \Theta(\log n)$

Эта игра известна?

reference-request graph-theory co.combinatorics graph-colouring decision-trees Юваль Фильмус
источник

Я думаю, что вы можете смоделировать это как игру Ehrenfeucht – Fraïssé .

Тайсон Уильямс

Казалось бы, это сильно связано с алгоритмами раскраски жадных графов, верно? из которых есть много .... аналогично проблемам SAT, когда одна из переменных "принудительно" после некоторого обхода DPLL ... которую я считаю также называемой "магистралью" в SAT

vzn

Почему вы используете d − 1? Я думаю, что более естественно параметризовать игру как по графу G, так и по количеству разрешенных цветов k и рассмотреть аналогичную величину X (G, k). Конечно, если k≥χ (G), то выигрывает Боб, и поэтому в этом случае X (G, k) следует определять как ∞ или n + 1.

Цуёси Ито

@Tsuyoshi: - произвольный выбор, разработанный для максимизации . В приложении, которое я имею в виду, не имеет смысла.

k = d - 1

$k = d-1$

X (G)

$X(G)$

k \geq χ (G)

$k \geq \chi(G)$

Ювал Фильмус

@Tyson: На самом деле - сложность дерева решений в игре, в которой, учитывая раскраску , мы хотим найти нарушенное ребро.

X (G)

$X(G)$

d - 1

$d-1$

G

$G$

Ювал Фильмус

Сложность раскраски графиков

Ответы: