Введение

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

Определение

Для заданного графа G и заданного множества L(v) цветов для каждой вершины v (называемого списком), раскраска по списку — это функция выбора, которая сопоставляет каждой вершине v цвет из списка L(v). Как и в случае обычной раскраски графа, раскраска по списку обычно предполагается правильной, то есть никакие две смежные вершины не получают один и тот же цвет. Граф называется k-выбираемым (или k-раскрашиваемым по списку), если он имеет правильную раскраску по списку, независимо от того, как назначены списки из k цветов каждой вершине. Выбираемость (или раскрашиваемость по списку, или хроматическое число списка) ch(G) графа G — это наименьшее число k, такое что G является k-выбираемым. В более общем случае, для функции f, присваивающей каждому вершине v положительное целое число f(v), граф G называется f-выбираемым (или f-раскрашиваемым по списку), если он имеет раскраску по списку, независимо от того, как назначены списки из f(v) цветов каждой вершине v. В частности, если для всех вершин v f-выбираемость соответствует k-выбираемости.

Примеры

Рассмотрим полный двудольный граф G = K2,4, имеющий шесть вершин A, B, W, X, Y, Z, таких что A и B соединены со всеми W, X, Y и Z, и никакие другие вершины не соединены. Как двудольный граф, G имеет обычное хроматическое число 2: можно окрасить A и B в один цвет, а W, X, Y, Z — в другой, и никакие две смежные вершины не будут иметь одинаковый цвет. С другой стороны, G имеет хроматическое число списка больше 2, как показывает следующая конструкция: присвойте A и B списки {красный, синий} и {зеленый, черный}. Определите остальные четыре вершины списками {красный, зеленый}, {красный, черный}, {синий, зеленый} и {синий, черный}. Независимо от того, какой цвет вы выберете из списка A и какой цвет из списка B, найдется другая вершина, для которой оба возможных цвета уже использованы для окрашивания ее соседей. Таким образом, G не является 2-выбираемым. С другой стороны, легко увидеть, что G 3-выбираем: выбор произвольных цветов для вершин A и B оставляет по крайней мере один доступный цвет для каждой из оставшихся вершин, и эти цвета могут быть выбраны произвольно. В более общем смысле, пусть q — положительное целое число, а G — полный двудольный граф Kq,qq. Пусть доступные цвета представлены q2 различными двузначными числами в системе счисления по основанию q. На одной стороне двудольного разбиения зададим вершинам q множества цветов {i0, i1, i2, ...}, в которых первые цифры равны друг другу для каждого из q возможных вариантов первой цифры i. На другой стороне двудольного разбиения зададим вершинам qq множества цветов {0a, 1b, 2c, ...}, в которых первые цифры все различны для каждого из qq возможных вариантов q-кортежа (a, b, c, ...). На иллюстрации показан более крупный пример той же конструкции, с q = 3. Тогда G не имеет раскраски списком для L: независимо от того, какой набор цветов выбран для вершин на малой стороне двудольного разбиения, этот выбор приведет к конфликту со всеми цветами для одной из вершин на другой стороне двудольного разбиения. Например, если вершина с набором цветов {00, 01} окрашена в 01, а вершина с набором цветов {10, 11} окрашена в 10, то вершина с набором цветов {01, 10} не может быть окрашена. Следовательно, хроматическое число списка для G не меньше q + 1. Аналогично, если n = k, то полный двудольный граф Kn,n не является k-выбираемым. Действительно, предположим, что всего доступно 2k − 1 цветов, и что на одной стороне двудольного разбиения каждая вершина имеет доступ к другому k-кортежу этих цветов, чем каждая другая вершина. Тогда каждая сторона двудольного разбиения должна использовать по крайней мере k цветов, поскольку каждый набор из k − 1 цветов будет не пересекаться со списком одной вершины. Поскольку по крайней мере k цветов используется с одной стороны и по крайней мере k цветов используется с другой, должен быть один цвет, который используется с обеих сторон, но это означает, что две смежные вершины имеют один и тот же цвет. В частности, граф полезности K3,3 имеет хроматическое число списка не менее трех, а граф K10,10 имеет хроматическое число списка не менее четырех.

Свойства

Для графа G обозначим χ(G) хроматическим числом, а Δ(G) – максимальной степенью графа G. Число раскраски по списку ch(G) обладает следующими свойствами: ch(G) ≥ χ(G). k-раскрашиваемый по списку граф, в частности, должен иметь раскраску по списку, когда каждой вершине присвоен один и тот же список из k цветов, что соответствует обычной k-раскраске. В общем случае, ch(G) нельзя ограничить через хроматическое число, то есть не существует функции f, такой что ch(G) ≤ f(χ(G)) для любого графа G. В частности, как показывают примеры полных двудольных графов, существуют графы с χ(G) = 2, но с ch(G), которое может быть сколь угодно большим. ch(G) ≤ Δ(G) + 1.
ch(G) ≤ 5, если G – планарный граф. ch(G) ≤ 3, если G – двудольный планарный граф.