Раскраска списка - List coloring

В теория графов, филиал математика, раскраска списка это тип раскраска графика где каждая вершина может быть ограничена списком разрешенных цветов. Впервые он был изучен в 1970-х годах в независимых работах. Визинг и по Erds, Вбивать в голову, и Тейлор.[1]

Определение

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

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

Примеры

Рассмотрим полную двудольный граф г = K2,4, имеющий шесть вершин А, B, W, Икс, Y, Z такой, что А и B каждый связан со всеми W, Икс, Y, и Z, и никакие другие вершины не связаны. Как двудольный граф, г имеет обычное хроматическое число 2: можно раскрасить А и B в одном цвете и W, Икс, Y, Z в другом и никакие две соседние вершины не будут иметь одинаковый цвет. С другой стороны, г имеет хроматическое число списка больше 2, как показывает следующая конструкция: присвоить А и B списки {красный, синий} и {зеленый, черный}. Присвойте остальным четырем вершинам списки {красный, зеленый}, {красный, черный}, {синий, зеленый} и {синий, черный}. Независимо от того, какой выбор делает цвет из списка А и цвет из списка B, будет какая-то другая вершина, оба варианта которой уже используются для окраски соседей. Таким образом, г не может быть 2-выбираемым.

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

Экземпляр раскраски списка на полный двудольный граф K3,27 с тремя цветами на вершину. Независимо от того, какие цвета выбраны для трех центральных вершин, одна из 27 внешних вершин будет неокрашенной, что показывает, что хроматическое число K3,27 не меньше четырех.

В общем, пусть q - натуральное число, и пусть г быть полный двудольный граф Kq,qq. Пусть доступные цвета будут представлены q2 разные двузначные числа в основание q.Пусть с одной стороны двудольного q вершинам даны наборы цветов {я0, я1, я2, ...}, в которых первые цифры равны друг другу, для каждой из q возможные варианты первой цифрыя.Пусть с другой стороны двудольного qq вершинам даны наборы цветов {0а, 1б, 2c, ...}, в котором все первые цифры различны, для каждой из qq возможные варианты qпара (а, б, c, ...).На иллюстрации показан более крупный пример такой же конструкции с q = 3.

Потом, г не имеет раскраски списка для L: независимо от того, какой набор цветов выбран для вершин на маленькой стороне двудольного раздела, этот выбор будет конфликтовать со всеми цветами для одной из вершин на другой стороне двудольного раздела. Например, если вершина с набором цветов {00,01} окрашена в 01, а вершина с набором цветов {10,11} окрашена в 10, то вершина с набором цветов {01,10} не может быть окрашена. Следовательно, список хроматического числа г по крайней мере q + 1.[2]

Аналогично, если , то полный двудольный граф Kп, п не является k-выбор. В самом деле, предположим, что 2k - Всего доступен 1 ​​цвет, и что на одной стороне двудольного разделения каждая вершина имеет свой доступный k-набор этих цветов, чем каждая другая вершина. Тогда каждая сторона двудольного деления должна использовать не менее k цвета, потому что каждый набор k - 1 цвет будет непересекающимся из списка одной вершины. Поскольку по крайней мере k цвета используются с одной стороны и не менее k используются с другой стороны, должен быть один цвет, который используется с обеих сторон, но это означает, что две соседние вершины имеют одинаковый цвет. В частности, график полезности K3,3 имеет список-хроматическое число не менее трех, а граф K10,10 имеет список-хроматическое число не менее четырех.[3]

Свойства

Для графика г, пусть χ (г) обозначают хроматическое число и Δ (г) максимальная степень из г. Список раскраски числа ch (г) удовлетворяет следующим свойствам.

  1. ch (г) ≥ χ (г). А kграф, раскрашиваемый списком, должен, в частности, иметь раскраску списка, когда каждой вершине назначается один и тот же список k цвета, что соответствует обычному k-раскрашивание.
  2. ch (г) не может быть ограничена по хроматическому числу вообще, то есть не существует функции ж такой, что ch (г) ≤ ж(χ (г)) выполняется для любого графа г. В частности, как показывают примеры полных двудольных графов, существуют графы с χ (г) = 2, но с ch (г) произвольно большой.[2]
  3. ch (г) ≤ χ (г) ln (п) где п количество вершин г.[4][5]
  4. ch (г) ≤ Δ (г) + 1.[3][6]
  5. ch (г) ≤ 5, если г это планарный граф.[7]
  6. ch (г) ≤ 3, если г это двудольный планарный граф.[8]

Возможность выбора и (а, б) -выбор

В литературе рассмотрены две алгоритмические проблемы:

  1. k-возможность выбора: решить, является ли данный граф k-выбор для данного k, и
  2. (а, б)-возможность выбора: решить, является ли данный граф ж-выбирается для данной функции .

Известно, что k-выбор в двудольных графах -комплект на любой k ≥ 3, и то же самое относится к 4-выбору в планарных графах, 3-выбору в плоских графах. графы без треугольников, и (2, 3) -выбор в двудольный планарные графы.[9][10] Для P5-свободные графы, то есть графы исключая 5-вершина граф путей, k-выбор есть управляемый с фиксированными параметрами.[11]

Можно проверить, является ли график 2-выбираемым в линейное время путем многократного удаления вершин нулевой или единичной степени до достижения 2-ядерный графика, после чего такие удаления становятся невозможными. Исходный граф является 2-выбираемым тогда и только тогда, когда его 2-ядро является либо четным циклом, либо тета-график образованный тремя путями с общими конечными точками, причем два пути имеют длину два, а третий путь имеет любую четную длину.[3]

Приложения

Раскраска списка возникает в практических задачах, касающихся присвоения каналов / частот.[12][13]

Смотрите также

использованная литература

  1. ^ Дженсен, Томми Р .; Тофт, Бьярн (1995), «1.9 Раскраска списка», Задачи раскраски графов, Нью-Йорк: Wiley-Interscience, стр. 18–21, ISBN  0-471-02865-7
  2. ^ а б Gravier, Sylvain (1996), "Теорема Хажоса для раскраски списка", Дискретная математика, 152 (1–3): 299–302, Дои:10.1016 / 0012-365X (95) 00350-6, Г-Н  1388650.
  3. ^ а б c Эрдеш, П.; Рубин, А.; Тейлор, Х. (1979), "Возможность выбора в графах", Proc. Конференция Западного побережья по комбинаторике, теории графов и вычислениям, Арката (PDF), Congressus Numerantium, 26, стр. 125–157, архивировано с оригинал (PDF) на 2016-03-09, получено 2008-11-10
  4. ^ Итон, Нэнси (2003), «О двух коротких доказательствах о раскраске списка - Часть 1» (PDF), Говорить, заархивировано из оригинал (PDF) 29 августа 2017 г., получено 29 мая, 2010
  5. ^ Итон, Нэнси (2003), «О двух коротких доказательствах о раскраске списка - Часть 2» (PDF), Говорить, заархивировано из оригинал (PDF) 30 августа 2017 г., получено 29 мая, 2010
  6. ^ Визинг, В.Г. (1976), «Раскраска вершин заданными цветами», Методы Дискрет. Анализ. (по-русски), 29: 3–10
  7. ^ Томассен, Карстен (1994), «Каждый плоский граф имеет 5-выборный выбор», Журнал комбинаторной теории, серия B, 62: 180–181, Дои:10.1006 / jctb.1994.1062
  8. ^ Алон, Нога; Тарси, Майкл (1992), "Раскраски и ориентации графов", Комбинаторика, 12: 125–134, Дои:10.1007 / BF01204715
  9. ^ Гутнер, Шай (1996), "Сложность выбора плоского графа", Дискретная математика, 159 (1): 119–130, arXiv:0802.2668, Дои:10.1016 / 0012-365X (95) 00104-5.
  10. ^ Гутнер, Шай; Тарси, Майкл (2009), «Некоторые результаты по (а:б) -выбор ", Дискретная математика, 309 (8): 2260–2270, Дои:10.1016 / j.disc.2008.04.061
  11. ^ Хеггернес, Пинар; Головач, Петр (2009), "Возможность выбора P5-бесплатные графики » (PDF), Математические основы компьютерных наук, Конспект лекций по информатике, 5734, Springer-Verlag, стр. 382–391.
  12. ^ Ван, Вэй; Лю, Синь (2005 г.), "Распределение каналов на основе цветного списка для беспроводных сетей с открытым спектром", 2005 IEEE 62-я Конференция по автомобильным технологиям (VTC 2005-осень), 1, стр. 690–694, Дои:10.1109 / VETECF.2005.1558001.
  13. ^ Garg, N .; Papatriantafilou, M .; Цигас П. (1996), "Распределенная окраска списка: как динамически распределять частоты для мобильных базовых станций", Восьмой симпозиум IEEE по параллельной и распределенной обработке, стр. 18–25, Дои:10.1109 / SPDP.1996.570312, HDL:21.11116 / 0000-0001-1AE6-F.

дальнейшее чтение