Раскраска графа

Methodic assignment of colors to elements of a graph

Правильная раскраска вершин графа Петерсена тремя цветами — минимально возможным числом.

В теории графов раскраска графа является частным случаем маркировки графа ; это назначение меток, традиционно называемых «цветами», элементам графа , подчиняющимся определенным ограничениям. В своей простейшей форме это способ раскраски вершин графа таким образом, что никакие две смежные вершины не имеют одинакового цвета; это называется раскраской вершины . Аналогично, раскраска ребер назначает цвет каждому ребру так, что никакие два смежных ребра не имеют одинакового цвета, а раскраска граней планарного графа назначает цвет каждой грани или области так, что никакие две грани, имеющие общую границу, не имеют одинакового цвета.

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

Соглашение об использовании цветов берет свое начало от раскраски стран карты , где каждая грань буквально раскрашена. Это было обобщено до раскраски граней графа, вложенного в плоскость. Благодаря плоскостной двойственности это стало раскраской вершин, и в этой форме это обобщается на все графы. В математических и компьютерных представлениях типично использовать первые несколько положительных или неотрицательных целых чисел в качестве «цветов». В общем, можно использовать любой конечный набор в качестве «набора цветов». Природа проблемы раскраски зависит от количества цветов, но не от того, какие они.

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

Примечание: многие термины, используемые в этой статье, определены в Глоссарии теории графов .

История

Карта Соединенных Штатов , на которой цвета показывают политическое деление с использованием теоремы о четырех цветах .

Первые результаты о раскраске графов касались почти исключительно планарных графов в форме раскраски карт . Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри выдвинул гипотезу о четырёх цветах , отметив, что четырёх цветов достаточно для раскраски карты так, чтобы никакие регионы, имеющие общую границу, не получили одинаковый цвет. Брат Гатри передал вопрос своему учителю математики Августу Де Моргану в Университетском колледже , который упомянул об этом в письме Уильяму Гамильтону в 1852 году. Артур Кейли поднял проблему на заседании Лондонского математического общества в 1879 году. В том же году Альфред Кемпе опубликовал статью, в которой утверждал, что установил результат, и в течение десятилетия проблема четырёх цветов считалась решённой. За своё достижение Кемпе был избран членом Королевского общества , а затем президентом Лондонского математического общества. ^[1]

В 1890 году Перси Джон Хивуд указал на то, что аргумент Кемпе был неверен. Однако в этой статье он доказал теорему о пяти красках , заявив, что каждая плоская карта может быть раскрашена не более чем пятью цветами, используя идеи Кемпе. В следующем столетии была проделана огромная работа и разработаны теории, чтобы сократить количество цветов до четырех, пока теорема о четырех красках не была окончательно доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном . Доказательство вернулось к идеям Хивуда и Кемпе и в значительной степени проигнорировало промежуточные разработки. ^[2] Доказательство теоремы о четырех красках примечательно, помимо решения им проблемы вековой давности, тем, что оно является первым крупным доказательством с помощью компьютера.

В 1912 году Джордж Дэвид Биркгоф ввел хроматический многочлен для изучения проблемы раскраски, который был обобщен до многочлена Тутта У. Т. Туттом , оба из которых являются важными инвариантами в алгебраической теории графов . Кемпе уже привлек внимание к общему, непланарному случаю в 1879 году ^[3], и многие результаты по обобщениям планарной раскраски графов на поверхности более высокого порядка последовали в начале 20-го века.

В 1960 году Клод Берже сформулировал еще одну гипотезу о раскраске графов, сильную гипотезу о совершенном графе , изначально мотивированную теоретико-информационной концепцией , называемой емкостью графа с нулевой ошибкой, введенной Шенноном . Гипотеза оставалась неразрешенной в течение 40 лет, пока она не была установлена ​​как знаменитая сильная теорема о совершенном графе Чудновским , Робертсоном , Сеймуром и Томасом в 2002 году.

Раскраска графов изучалась как алгоритмическая проблема с начала 1970-х годов: задача хроматического числа (см. раздел § Раскраска вершин ниже) является одной из 21 NP-полных задач Карпа с 1972 года, и примерно в то же время были разработаны различные алгоритмы с экспоненциальным временем, основанные на откате и на рекуррентности удаления-сокращения Зыкова (1949). Одно из основных приложений раскраски графов, распределение регистров в компиляторах, было представлено в 1981 году.

Определения и терминология

Этот график можно раскрасить в 3 цвета 12 различными способами.

Раскраска вершин

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

Терминология использования цветов для меток вершин восходит к раскраске карт. Метки типа красный и синий используются только тогда, когда количество цветов невелико, и обычно подразумевается, что метки берутся из целых чисел {1, 2, 3, ...} .

Раскраска, использующая не более k цветов, называется (правильной) k -раскраской . Наименьшее количество цветов, необходимое для раскраски графа G, называется его хроматическим числом и часто обозначается χ( G ) . Иногда используется γ( G ) , поскольку χ( G ) также используется для обозначения эйлеровой характеристики графа. Граф, которому можно назначить (правильную) k -раскраску, является k -раскрашиваемым , и он является k -хроматическим, если его хроматическое число равно ровно k . Подмножество вершин, которым назначен один и тот же цвет, называется классом цветов , каждый такой класс образует независимое множество . Таким образом, k -раскраска совпадает с разбиением множества вершин на k независимых множеств, а термины k -раздельный и k -раскрашиваемый имеют одинаковое значение.

Хроматический многочлен

Все неизоморфные графы на 3 вершинах и их хроматические многочлены. Пустой граф E ₃ (красный) допускает 1-раскраску; полный граф K ₃ (синий) допускает 3-раскраску; остальные графы допускают 2-раскраску.

Хроматический многочлен подсчитывает количество способов, которыми граф может быть раскрашен с использованием некоторого из заданного количества цветов. Например, используя три цвета, граф на соседнем изображении можно раскрасить 12 способами. Используя только два цвета, его вообще нельзя раскрасить. Используя четыре цвета, его можно раскрасить 24 + 4 × 12 = 72 способами: используя все четыре цвета, есть 4! = 24 допустимых раскрасок ( каждое назначение четырех цветов любому графу с 4 вершинами является правильной раскраской); и для каждого выбора трех из четырех цветов есть 12 допустимых 3-раскрасок. Таким образом, для графа в примере таблица количества допустимых раскрасок будет начинаться так:

Хроматический многочлен — это функция P ( G , t ) , которая подсчитывает количество t -раскрасок графа G . Как следует из названия, для заданного G функция действительно является многочленом по t . Для графа-примера P ( G , t ) = t ( t − 1) ² ( t − 2) , и действительно P ( G , 4) = 72 .

Хроматический многочлен содержит больше информации о раскрашиваемости G , чем хроматическое число. Действительно, χ — наименьшее положительное целое число, которое не является нулем хроматического многочлена χ( G ) = min{ k  : P ( G , k ) > 0} .

Окраска кромок

Раскраска ребер графа — это правильная раскраска ребер , то есть назначение цветов ребрам таким образом, чтобы ни одна вершина не инцидентна двум ребрам одного цвета. Раскраска ребер с k цветами называется k -раскраской ребер и эквивалентна задаче разбиения множества ребер на k паросочетаний . Наименьшее количество цветов, необходимое для раскраски ребер графа G , — это хроматический индекс , или хроматическое число ребер , χ ′( G ) . Раскраска Тейта — это 3-реберная раскраска кубического графа . Теорема о четырех цветах эквивалентна утверждению, что любой плоский кубический граф без мостов допускает раскраску Тейта.

Полная окраска

Полная раскраска — это тип раскраски вершин и ребер графа. При использовании без каких-либо оговорок полная раскраска всегда считается правильной в том смысле, что никакие смежные вершины, никакие смежные ребра и никакое ребро и его конечные вершины не имеют одного и того же цвета. Полное хроматическое число χ ″( G ) графа G — это наименьшее количество цветов, необходимых для любой полной раскраски G .

Раскрашивание лица

Для графа с сильным вложением на поверхности задача раскраски граней является двойственной по отношению к задаче раскраски вершин.

Теория потока Тутта

Для графа G с сильным вложением на ориентируемой поверхности Уильям Т. Татте ^{[4] [5] [6]} обнаружил, что если граф является k -гранно-раскрашиваемым, то G допускает нигде не нулевой k -поток. Эквивалентность сохраняется, если поверхность является сферой.

Немаркированная окраска

Немаркированная раскраска графа — это орбита раскраски под действием группы автоморфизмов графа. Цвета остаются помеченными; граф остается немаркированным. Существует аналог хроматического многочлена , который подсчитывает количество непомеченных раскрасок графа из заданного конечного набора цветов.

Если интерпретировать раскраску графа на d вершинах как вектор в ⁠ ⁠ ${\displaystyle \mathbb {Z} ^{d}}$ , то действие автоморфизма представляет собой перестановку коэффициентов в векторе раскраски.

Характеристики

Верхние границы хроматического числа

Назначение различных цветов различным вершинам всегда дает правильную раскраску, поэтому

${\displaystyle 1\leq \chi (G)\leq n.}$

Единственные графы, которые могут быть 1-цветными, — это графы без рёбер . Полный граф из n вершин требует цветов. В оптимальной раскраске должно быть по крайней мере одно из m ребер графа между каждой парой цветовых классов, поэтому ${\displaystyle K_{n}}$ ${\displaystyle \chi (K_{n})=n}$

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}$

В более общем случае семейство графов является χ -ограниченным, если существует некоторая функция , такая что графы в можно раскрасить не более чем в 0 цветов; для семейства совершенных графов эта функция равна . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle c(\omega (G))}$ ${\displaystyle c(\omega (G))=\omega (G)}$

Графы, которые можно раскрасить в 2 цвета, — это в точности двудольные графы , включая деревья и леса. По теореме о четырех цветах любой планарный граф можно раскрасить в 4 цвета.

Жадная раскраска показывает, что каждый граф можно раскрасить на один цвет больше, чем максимальная степень вершины ,

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

Полные графы имеют и , а нечетные циклы имеют и , поэтому для этих графов эта граница является наилучшей возможной. Во всех других случаях граница может быть немного улучшена; теорема Брукса ^[7] утверждает, что ${\displaystyle \chi (G)=n}$ ${\displaystyle \Delta (G)=n-1}$ ${\displaystyle \chi (G)=3}$ ${\displaystyle \Delta (G)=2}$

Теорема Брукса : для связного простого графа G , если только G не является полным графом или нечетным циклом. ${\displaystyle \chi (G)\leq \Delta (G)}$

Нижние границы хроматического числа

За прошедшие годы было обнаружено несколько нижних границ хроматических границ:

Если G содержит клику размера k , то для раскрашивания этой клики требуется не менее k цветов; другими словами, хроматическое число не меньше номера клики:

${\displaystyle \chi (G)\geq \omega (G).}$

Для идеальных графов эта граница узкая. Поиск клик известен как проблема клик .

Граница Хоффмана: Пусть будет вещественной симметричной матрицей, такой что всякий раз, когда не является ребром в . Определим , где — наибольшее и наименьшее собственные значения . Определим , как и выше. Тогда: ${\displaystyle W}$ ${\displaystyle W_{i,j}=0}$ ${\displaystyle (i,j)}$ ${\displaystyle G}$ ${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$ ${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$ ${\displaystyle W}$ ${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$ ${\displaystyle W}$

${\displaystyle \chi _{H}(G)\leq \chi (G).}$

Вектор хроматического числа :Пустьбудет положительной полуопределенной матрицей, такой чтовсякий раз, когдаесть ребро в. Определимкак наименьшее k, для которого существует такая матрица. Тогда ${\displaystyle W}$ ${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$ ${\displaystyle (i,j)}$ ${\displaystyle G}$ ${\displaystyle \chi _{V}(G)}$ ${\displaystyle W}$

${\displaystyle \chi _{V}(G)\leq \chi (G).}$

Число Ловаса : Число Ловаса дополнительного графа также является нижней границей хроматического числа:

${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

Дробное хроматическое число : Дробное хроматическое число графа также является нижней границей хроматического числа:

${\displaystyle \chi _{f}(G)\leq \chi (G).}$

Эти границы упорядочены следующим образом:

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

Графы с высоким хроматическим числом

Графы с большими кликами имеют высокое хроматическое число, но обратное неверно. Граф Грётша является примером 4-хроматического графа без треугольника, и пример может быть обобщен до Mycielskians .

Теорема ( Уильям Т. Тутт  1947, ^[8] Александр Зыков 1949, Ян Мычельский  1955): Существуют графы без треугольников с произвольно большим хроматическим числом.

Чтобы доказать это, и Мычельский, и Зыков, каждый из них дали конструкцию индуктивно определенного семейства графов без треугольников, но с произвольно большим хроматическим числом. ^[9] Берлинг (1965) построил выровненные по осям блоки, в графе пересечений которых нет треугольников и для правильной раскраски требуется произвольное количество цветов. Это семейство графов затем называется графами Берлинга. Тот же класс графов используется для построения семейства отрезков прямых без треугольников на плоскости, заданного Пауликом и др. (2014). ^[10] Это показывает, что хроматическое число его графа пересечений также произвольно велико. Следовательно, это означает, что выровненные по осям блоки в , а также отрезки прямых в не являются χ -ограниченными . ^[10] ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} ^{2}}$

Из теоремы Брукса, графы с высоким хроматическим числом должны иметь высокую максимальную степень. Но раскрашиваемость — это не совсем локальное явление: граф с высоким обхватом локально выглядит как дерево, потому что все циклы длинные, но его хроматическое число не обязательно должно быть 2:

Теорема ( Эрдёша ): Существуют графы произвольно большого обхвата и хроматического числа. ^[11]

Границы хроматического индекса

Раскраска ребер графа G является раскраской вершин его линейного графа , и наоборот. Таким образом, ${\displaystyle L(G)}$

${\displaystyle \chi '(G)=\chi (L(G)).}$

Существует сильная связь между раскрашиваемостью ребер и максимальной степенью графа . Поскольку все ребра, инцидентные одной вершине, должны иметь свой собственный цвет, мы имеем ${\displaystyle \Delta (G)}$

${\displaystyle \chi '(G)\geq \Delta (G).}$

Более того,

Теорема Кёнига : если G двудольный. ${\displaystyle \chi '(G)=\Delta (G)}$

В общем случае эта связь даже сильнее, чем та, которую дает теорема Брукса для раскраски вершин:

Теорема Визинга: Граф максимальной степениимеет реберно-хроматическое числоили. ${\displaystyle \Delta }$ ${\displaystyle \Delta }$ ${\displaystyle \Delta +1}$

Другие свойства

Граф имеет k -раскраску тогда и только тогда, когда он имеет ациклическую ориентацию , для которой самый длинный путь имеет длину не более k ; это теорема Галлаи–Хассе–Роя–Витавера (Nešetřil & Ossona de Mendez 2012).

Для планарных графов раскраска вершин по сути является двойственной по отношению к потокам, не имеющим нулевого значения .

О бесконечных графах известно гораздо меньше. Ниже приведены два из немногих результатов о бесконечной раскраске графов:

• Если все конечные подграфы бесконечного графа G являются k -раскрашиваемыми, то таковым является и G , при условии аксиомы выбора . Это теорема де Брейна–Эрдёша де Брейна и Эрдёша (1951).
• Если граф допускает полную n -раскраску для каждого n ≥ n ₀ , то он допускает бесконечную полную раскраску (Фосетт, 1978).

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

Как указано выше, гипотеза Рида от 1998 года заключается в том, что значение по существу ближе к нижней границе, ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$ ${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

Хроматическое число плоскости , где две точки являются смежными, если они находятся на единичном расстоянии, неизвестно, хотя оно может быть одним из 5, 6 или 7. Другие открытые проблемы, касающиеся хроматического числа графов, включают гипотезу Хадвигера, утверждающую, что каждый граф с хроматическим числом k имеет полный граф на k вершинах в качестве минора , гипотезу Эрдёша–Фабера–Ловаса, ограничивающую хроматическое число объединений полных графов, которые имеют не более одной общей вершины для каждой пары, и гипотезу Альбертсона , что среди k -хроматических графов полные графы — это графы с наименьшим числом пересечений .

Когда Биркгоф и Льюис ввели хроматический многочлен в своей атаке на теорему о четырех красках, они предположили, что для планарных графов G многочлен не имеет нулей в области . Хотя известно, что такой хроматический многочлен не имеет нулей в области и что , их гипотеза все еще не решена. Также остается нерешенной проблема характеризации графов, имеющих один и тот же хроматический многочлен, и определения того, какие многочлены являются хроматическими. ${\displaystyle P(G,t)}$ ${\displaystyle [4,\infty )}$ ${\displaystyle [5,\infty )}$ ${\displaystyle P(G,4)\neq 0}$

Алгоритмы

Полиномиальное время

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

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

Точные алгоритмы

Поиск методом грубой силы для k -раскраски рассматривает каждое из назначений k цветов n вершинам и проверяет для каждого, является ли оно допустимым. Для вычисления хроматического числа и хроматического многочлена эта процедура используется для каждого , непрактично для всех, кроме самых маленьких входных графов. ${\displaystyle k^{n}}$ ${\displaystyle k=1,\ldots ,n-1}$

Используя динамическое программирование и ограничение на число максимальных независимых множеств , k -раскрашиваемость может быть определена за время и пространство . ^[13] Используя принцип включения-исключения и алгоритм Йейтса для быстрого дзета-преобразования, k -раскрашиваемость может быть определена за время ^{[12] [14] [15] [16]} для любого k . Более быстрые алгоритмы известны для 3- и 4-раскрашиваемости, которые могут быть определенны за время ^[17] и , ^[18] соответственно. Экспоненциально более быстрые алгоритмы также известны для 5- и 6-раскрашиваемости, а также для ограниченных семейств графов, включая разреженные графы. ^[19] ${\displaystyle O(2.4423^{n})}$ ${\displaystyle O(2^{n}n)}$ ${\displaystyle O(1.3289^{n})}$ ${\displaystyle O(1.7272^{n})}$

Сокращение

Сжатие графа G — это граф, полученный путем идентификации вершин u и v и удаления всех ребер между ними. Оставшиеся ребра, изначально инцидентные u или v , теперь инцидентны их идентификации ( т. е . новому объединенному узлу uv ). Эта операция играет важную роль в анализе раскраски графа. ${\displaystyle G/uv}$

Хроматическое число удовлетворяет рекуррентному соотношению :

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

из-за Зыкова (1949), где u и v — несмежные вершины, а — граф с добавленным ребром uv . Несколько алгоритмов основаны на оценке этой рекуррентности, и полученное вычислительное дерево иногда называют деревом Зыкова. Время выполнения основано на эвристике выбора вершин u и v . ${\displaystyle G+uv}$

Хроматический многочлен удовлетворяет следующему рекуррентному соотношению:

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}$

где u и v — смежные вершины, а — граф с удаленным ребром uv . представляет собой число возможных правильных раскрасок графа, где вершины могут иметь одинаковые или разные цвета. Тогда правильные раскраски возникают из двух разных графов. Чтобы объяснить, если вершины u и v имеют разные цвета, то мы могли бы также рассмотреть граф, в котором u и v являются смежными. Если u и v имеют одинаковые цвета, мы могли бы также рассмотреть граф, в котором u и v стянуты. Любопытство Тутта о том, какие другие свойства графа удовлетворяют этой рекуррентности, привело его к открытию двумерного обобщения хроматического многочлена, многочлена Тутта . ${\displaystyle G-uv}$ ${\displaystyle P(G-uv,k)}$

Эти выражения порождают рекурсивную процедуру, называемую алгоритмом удаления-сжатия , которая составляет основу многих алгоритмов раскраски графов. Время выполнения удовлетворяет тому же рекуррентному соотношению, что и числа Фибоначчи , поэтому в худшем случае алгоритм выполняется за время в пределах полиномиального множителя для n вершин и m ребер. ^[20] Анализ можно улучшить до полиномиального множителя числа остовных деревьев входного графа. ^[21] На практике стратегии ветвей и границ и отклонение изоморфизма графа используются для того, чтобы избежать некоторых рекурсивных вызовов. Время выполнения зависит от эвристики, используемой для выбора пары вершин. ${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$ ${\displaystyle t(G)}$

Жадная раскраска

Две жадные раскраски одного и того же графа с использованием разных порядков вершин. Правый пример обобщается до 2-раскрашиваемых графов с n вершинами, где жадный алгоритм расходует цвета. ${\displaystyle n/2}$

Жадный алгоритм рассматривает вершины в определенном порядке , ..., и назначает наименьший доступный цвет, не используемый соседями среди , ..., , добавляя новый цвет при необходимости. Качество результирующей раскраски зависит от выбранного порядка. Существует порядок, который приводит к жадной раскраске с оптимальным количеством цветов. С другой стороны, жадные раскраски могут быть сколь угодно плохими; например, граф короны на n вершинах может быть 2-цветным, но имеет порядок, который приводит к жадной раскраске с цветами. ${\displaystyle v_{1}}$ ${\displaystyle v_{n}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{i-1}}$ ${\displaystyle \chi (G)}$ ${\displaystyle n/2}$

Для хордовых графов и для особых случаев хордовых графов, таких как интервальные графы и безразличные графы , алгоритм жадной раскраски может быть использован для поиска оптимальных раскрасок за полиномиальное время, выбирая порядок вершин, обратный совершенному порядку исключения для графа. Совершенно упорядочиваемые графы обобщают это свойство, но найти совершенное упорядочение этих графов NP-трудно.

Если вершины упорядочены в соответствии с их степенями , то результирующая жадная раскраска использует не более цветов, не более чем на один больше максимальной степени графа. Эту эвристику иногда называют алгоритмом Уэлша-Пауэлла. ^[22] Другая эвристика, созданная Брелазом, устанавливает порядок динамически, пока алгоритм продолжает работу, выбирая следующую вершину, смежную с наибольшим числом различных цветов. ^[23] Многие другие эвристики раскраски графов также основаны на жадной раскраске для определенной статической или динамической стратегии упорядочения вершин, эти алгоритмы иногда называют алгоритмами последовательной раскраски . ${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$

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

Эвристические алгоритмы

Два известных эвристических алгоритма полиномиального времени для раскраски графов — это алгоритм DSatur и рекурсивный алгоритм наибольшего первого элемента (RLF).

Подобно алгоритму жадной раскраски , DSatur раскрашивает вершины графа одну за другой, расходуя ранее неиспользованный цвет при необходимости. После того, как новая вершина раскрашена, алгоритм определяет, какая из оставшихся неокрашенных вершин имеет наибольшее количество различных цветов в своем окружении, и раскрашивает эту вершину следующей. Это определяется как степень насыщенности данной вершины.

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

Худшая сложность DSatur равна , где — число вершин в графе. Алгоритм также может быть реализован с использованием двоичной кучи для хранения степеней насыщения, работающей в , где — число ребер в графе. ^[24] Это обеспечивает гораздо более быстрые запуски с разреженными графами. Общая сложность RLF немного выше, чем DSatur , при . ^[24] ${\displaystyle O(n^{2})}$ ${\displaystyle n}$ ${\displaystyle O((n+m)\log n)}$ ${\displaystyle m}$ ${\displaystyle O(mn)}$

DSatur и RLF точны для двудольных , циклических и колесных графов . ^[24]

Параллельные и распределенные алгоритмы

Известно, что χ -хроматический граф может быть c -раскрашен в детерминированной модели LOCAL за . раундов, с . Также известна соответствующая нижняя граница раундов. Эта нижняя граница сохраняется, даже если разрешены квантовые компьютеры, которые могут обмениваться квантовой информацией, возможно, с предварительно общим запутанным состоянием. ${\displaystyle O(n^{1/\alpha })}$ ${\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }$ ${\displaystyle \Omega (n^{1/\alpha })}$

В области распределенных алгоритмов раскраска графа тесно связана с проблемой нарушения симметрии . Современные рандомизированные алгоритмы быстрее для достаточно большой максимальной степени Δ, чем детерминированные алгоритмы. Самые быстрые рандомизированные алгоритмы используют технику многократных испытаний Шнайдера и Ваттенхофера. ^[25]

В симметричном графе детерминированный распределенный алгоритм не может найти правильную раскраску вершин. Для нарушения симметрии необходима некоторая вспомогательная информация. Стандартное предположение заключается в том, что изначально каждый узел имеет уникальный идентификатор , например , из набора {1, 2, ..., n }. Иначе говоря, мы предполагаем, что нам дана n -раскраска. Задача состоит в том, чтобы уменьшить количество цветов с n до, например, Δ + 1. Чем больше цветов используется, например, O (Δ) вместо Δ + 1, тем меньше раундов связи требуется. ^[25]

Простая распределенная версия жадного алгоритма для (Δ + 1)-раскраски в худшем случае требует Θ( n ) раундов связи — может потребоваться распространение информации с одной стороны сети на другую.

Простейшим интересным случаем является n - цикл . Ричард Коул и Узи Вишкин ^[26] показывают, что существует распределенный алгоритм, который сокращает количество цветов с n до O (log  n ) за один синхронный шаг коммуникации. Повторяя ту же процедуру, можно получить 3-раскраску n- цикла за O ( log *  n ) шагов коммуникации (предполагая, что у нас есть уникальные идентификаторы узлов).

Функция log * , итерированный логарифм , является чрезвычайно медленно растущей функцией, "почти константой". Поэтому результат Коула и Вишкина поднял вопрос о том, существует ли распределенный алгоритм постоянного времени для 3-раскраски n -цикла. Linial (1992) показал, что это невозможно: любой детерминированный распределенный алгоритм требует Ω( log *  n ) шагов связи для сведения n -раскраски к 3-раскраске в n -цикле.

Метод Коула и Вишкина может быть применен также к произвольным графам ограниченной степени; время выполнения составляет poly(Δ) + O ( log *  n ). ^[27] Метод был распространен на графы единичных дисков Шнайдером и Ваттенхофером. ^[28] Самые быстрые детерминированные алгоритмы для (Δ + 1)-раскраски для малых Δ принадлежат Леониду Баренбойму, Майклу Элкину и Фабиану Куну. ^[29] Алгоритм Баренбойма и др. работает за время O (Δ) +  log * ( n )/2, что является оптимальным с точки зрения n , поскольку постоянный множитель 1/2 не может быть улучшен из-за нижней границы Линиала. Панконези и Шринивасан (1996) используют сетевые разложения для вычисления Δ+1-раскраски за время . ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$

Проблема раскраски ребер также изучалась в распределенной модели. Panconesi & Rizzi (2001) достигли (2Δ − 1)-раскраски за время O (Δ +  log *  n ) в этой модели. Нижняя граница для распределенной раскраски вершин, полученная Linial (1992), применима и к проблеме распределенной раскраски ребер.

Децентрализованные алгоритмы

Децентрализованные алгоритмы — это те, в которых не допускается передача сообщений (в отличие от распределенных алгоритмов, в которых происходит локальная передача сообщений), и существуют эффективные децентрализованные алгоритмы, которые раскрашивают граф, если существует правильная раскраска. Они предполагают, что вершина способна определять, использует ли какой-либо из ее соседей тот же цвет, что и вершина, т. е. существует ли локальный конфликт. Это умеренное предположение во многих приложениях, например, при распределении беспроводных каналов обычно разумно предположить, что станция сможет определить, используют ли другие мешающие передатчики тот же канал (например, путем измерения SINR). Эта информация о зондировании достаточна, чтобы позволить алгоритмам, основанным на обучающихся автоматах, находить правильную раскраску графа с вероятностью единица. ^[30]

Сложность вычислений

Раскраска графа вычислительно сложна. NP-полной задачей является решение вопроса, допускает ли заданный граф k -раскраску для заданного k, за исключением случаев k ∈ {0,1,2}. В частности, NP-полной задачей является вычисление хроматического числа. ^[31] Задача 3-раскраски остается NP-полной даже для 4-регулярных планарных графов . ^[32] Однако для графов с максимальной степенью 3 или меньше теорема Брукса подразумевает, что задача 3-раскраски может быть решена за линейное время. Кроме того, для каждого k > 3 k -раскраска планарного графа существует по теореме о четырех цветах , и такую ​​раскраску можно найти за полиномиальное время. Однако нахождение лексикографически наименьшей 4-раскраски планарного графа является NP-полной задачей. ^[33]

Самый известный алгоритм приближения вычисляет раскраску размером не более чем в пределах множителя O ( n (log log  n ) ² (log n) ⁻³ ) от хроматического числа. ^[34] Для всех ε  > 0 приближение хроматического числа в пределах n ^{1− ε} является NP-трудной задачей . ^[35]

Также NP-трудно раскрасить 3-цветный граф в 5 цветов, ^[36] 4-цветный граф в 7 цветов, ^[36] и k -цветный граф в цвета для k ≥ 5. ^[37] ${\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1}$

Вычисление коэффициентов хроматического многочлена является ♯P-трудной задачей . Фактически, даже вычисление значения является ♯P-трудной задачей в любой рациональной точке k, за исключением k  = 1 и k  = 2. ^[38] Не существует FPRAS для вычисления хроматического многочлена в любой рациональной точке k  ≥ 1,5, за исключением k  = 2, если только NP  =  RP . ^[39] ${\displaystyle \chi (G,k)}$

Для раскраски рёбер доказательство результата Визинга даёт алгоритм, который использует не более Δ+1 цветов. Однако выбор между двумя кандидатами на хроматическое число рёбер является NP-полным. ^[40] С точки зрения алгоритмов аппроксимации алгоритм Визинга показывает, что хроматическое число рёбер может быть аппроксимировано с точностью до 4/3, а результат по жёсткости показывает, что не существует (4/3 −  ε )-алгоритма для любого ε > 0, если только P = NP . Это одни из старейших результатов в литературе по алгоритмам аппроксимации, хотя ни одна из статей явно не использует это понятие. ^[41]

Приложения

Планирование

Модели раскраски вершин для ряда задач планирования . ^[42] В самой чистой форме заданный набор заданий должен быть назначен временным интервалам, каждому заданию требуется один такой интервал. Задания могут быть запланированы в любом порядке, но пары заданий могут конфликтовать в том смысле, что они не могут быть назначены на один и тот же временной интервал, например, потому что они оба полагаются на общий ресурс. Соответствующий граф содержит вершину для каждого задания и ребро для каждой конфликтующей пары заданий. Хроматическое число графа в точности равно минимальному makespan , оптимальному времени для завершения всех заданий без конфликтов.

Детали задачи планирования определяют структуру графа. Например, при назначении самолетов на рейсы результирующий граф конфликтов является интервальным графом , поэтому проблема раскраски может быть решена эффективно. При распределении полосы пропускания радиостанциям результирующий граф конфликтов является графом единичного диска , поэтому проблема раскраски является 3-аппроксимируемой.

Распределение регистров

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

Подход к этой проблеме в учебнике заключается в ее моделировании как проблемы раскраски графа. ^[43] Компилятор создает интерференционный граф , где вершины являются переменными, а ребро соединяет две вершины, если они нужны одновременно. Если граф можно раскрасить k цветами, то любой набор переменных, необходимых одновременно, можно сохранить не более чем в k регистрах.

Другие приложения

Проблема раскрашивания графа возникает во многих практических областях, таких как составление расписания спортивных мероприятий, ^[44] разработка планов рассадки, ^[45] составление расписания экзаменов, ^[46] составление расписания такси, ^[47] и решение головоломок судоку . ^[48]

Другие раскраски

теория Рамсея

Важный класс проблем неправильной раскраски изучается в теории Рамсея , где рёбрам графа назначаются цвета, и нет ограничений на цвета инцидентных рёбер. Простым примером является теорема о друзьях и незнакомцах , которая гласит, что при любой раскраске рёбер , полного графа из шести вершин, будет одноцветный треугольник; часто иллюстрируют, говоря, что любая группа из шести человек имеет либо трёх общих незнакомцев, либо трёх общих знакомых. Теория Рамсея занимается обобщениями этой идеи для поиска регулярности среди беспорядка, находя общие условия для существования одноцветных подграфов с заданной структурой. ${\displaystyle K_{6}}$

Другие раскраски

Раскрашивание также можно рассматривать для знаковых графиков и графиков усиления .

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

• Критический график
• Игра раскраска графов
• Гомоморфизм графа
• Строительство Hajós
• Математика судоку
• Многодольный граф
• Уникально раскрашиваемый график

Примечания

1. М. Кубале, История раскраски графов , в Кубале (2004).
2. ван Линт и Уилсон (2001), гл. 33.
3. Дженсен и Тофт (1995), стр. 2.
4. Тутте (1949)
5. Тутте (1954)
6. Чжан (1997)
7. Брукс (1941).
8. Декарт (1947).
9. Скотт и Сеймур (2020).
10. Паулик и др. (2014).
11. Эрдёш (1959).
12. Бьорклунд, Хусфельдт и Койвисто (2009), стр. 550.
13. Лоулер (1976).
14. Йейтс (1937), стр. 66-67.
15. Кнут (1997), Глава 4.6.4, стр. 501-502.
16. Койвисто (2004), стр. 45, 96–103.
17. Бейгель и Эппштейн (2005).
18. Фомин, Гасперс и Саурабх (2007).
19. Замир (2021).
20. Вильф (1986).
21. Секине, Имаи и Тани (1995).
22. Уэлш и Пауэлл (1967).
23. Брелаз (1979).
24. Льюис (2021).
25. Шнайдер и Ваттенхофер (2010).
26. Коул и Вишкин (1986), см. также Кормен, Лейзерсон и Ривест (1990, раздел 30.5).
27. Голдберг, Плоткин и Шеннон (1988).
28. Шнайдер и Ваттенхофер (2008).
29. Баренбойм и Элкин (2009); Кун (2009).
30. Например, см. Leith & Clifford (2006) и Duffy, O'Connell & Sapozhnikov (2008).
31. Гари, Джонсон и Стокмейер (1974); Гэри и Джонсон (1979).
32. Дэйли (1980).
33. Хуллер и Вазирани (1991).
34. Халлдорссон (1993).
35. Цукерман (2007).
36. Булин, Крохин и Опршал (2019).
37. Врохна и Живны (2020).
38. Джегер, Вертиган и Уэлш (1990).
39. Голдберг и Джеррум (2008).
40. Холиер (1981).
41. Крещенци и Канн (1998).
42. Маркс (2004).
43. Чайтин (1982).
44. Льюис (2021), стр. 221–246, Глава 8: Проектирование спортивных лиг.
45. Льюис (2021), стр. 203–220, Глава 7: Разработка планов рассадки.
46. Льюис (2021), стр. 247–276, Глава 9: Разработка университетских расписаний.
47. Льюис (2021), стр. 5–6, Раздел 1.1.3: Планирование такси.
48. Льюис (2021), стр. 172–179, Раздел 6.4: Латинские квадраты и головоломки судоку.

Ссылки

• Баренбойм, Л.; Элкин, М. (2009), «Распределенная (Δ + 1) -раскраска за линейное (по Δ ) время», Труды 41-го симпозиума по теории вычислений , стр. 111–120, arXiv : 0812.1379 , doi :10.1145/1536414.1536432, ISBN 978-1-60558-506-2, S2CID  13446345
• Бейгель, Р.; Эппштейн, Д. (2005), «3-раскраска во времени O (1,3289 ⁿ ) », Journal of Algorithms , 54 (2)): 168–204, arXiv : cs/0006046 , doi : 10.1016/j.jalgor.2004.06 .008, S2CID  1209067
• Бьёрклунд, А.; Хусфельдт, Т.; Койвисто, М. (2009), «Разбиение множеств с помощью включения–исключения», SIAM Journal on Computing , 39 (2): 546–563, doi :10.1137/070683933
• Брелаз, Д. (1979), «Новые методы раскраски вершин графа», Сообщения ACM , 22 (4): 251–256, doi : 10.1145/359094.359101 , S2CID  14838769
• Брукс, Р. Л. (1941), «О раскраске узлов сети», Труды Кембриджского философского общества , 37 (2): 194–197, Bibcode : 1941PCPS...37..194B, doi : 10.1017/S030500410002168X, S2CID  209835194
• de Bruijn, NG ; Erdős, P. (1951), "Проблема цвета для бесконечных графов и проблема в теории отношений" (PDF) , Nederl. Akad. Wetensch. Proc. Ser. A , 54 : 371–373, doi :10.1016/S1385-7258(51)50053-7, архивировано из оригинала (PDF) 2016-03-10 , извлечено 2009-05-16(= Индаг. Математика 13 )
• Булин, Й.; Крохин, А.; Опршал, Й. (2019), «Алгебраический подход к удовлетворению ограничений обещаний», Труды 51-го ежегодного симпозиума ACM SIGACT по теории вычислений , стр. 602–613, arXiv : 1811.00970 , doi : 10.1145/3313276.3316300 , ISBN 978-1-4503-6705-9
• Берлинг, Джеймс Перкинс (1965), О проблемах раскраски семейств прототипов (диссертация доктора философии), Боулдер: Университет Колорадо
• Бысков, Дж. М. (2004), «Перечисление максимальных независимых множеств с применением к раскраске графов», Operations Research Letters , 32 (6): 547–556, doi :10.1016/j.orl.2004.03.002
• Чайтин, Г. Дж. (1982), «Выделение и сброс регистров с помощью раскраски графов», Proc. 1982 SIGPLAN Symposium on Compiler Construction , стр. 98–105, doi :10.1145/800230.806984, ISBN 0-89791-074-5, S2CID  16872867
• Коул, Р.; Вишкин, У. (1986), «Детерминированное подбрасывание монеты с применением к оптимальному параллельному ранжированию списков», Информация и управление , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7
• Кормен, TH; Лейзерсон, CE; Ривест, RL (1990), Введение в алгоритмы (1-е изд.), The MIT Press
• Crescenzi, P.; Kann, V. (декабрь 1998 г.), «Как найти наилучшие результаты аппроксимации – продолжение Garey and Johnson», ACM SIGACT News , 29 (4): 90, doi : 10.1145/306198.306210 , S2CID  15748200
• Дейли, Д.П. (1980), «Единственность раскрашиваемости и раскрашиваемость планарных 4-регулярных графов являются NP-полными», Дискретная математика , 30 (3): 289–293, doi : 10.1016/0012-365X(80)90236-8
• Декарт, Бланш (апрель 1947), «Проблема с тремя красками», Эврика , 21
• Даффи, К.; О'Коннелл, Н.; Сапожников, А. (2008), «Анализ сложности децентрализованного алгоритма раскраски графа» (PDF) , Information Processing Letters , 107 (2): 60–63, doi :10.1016/j.ipl.2008.01.002
• Эрдёш, Пол (1959), «Теория графов и вероятность», Канадский математический журнал , 11 : 34–38, doi : 10.4153/CJM-1959-003-9 , S2CID  122784453
• Fawcett, BW (1978), «О бесконечных полных раскрасках графов», Can. J. Math. , 30 (3): 455–457, doi : 10.4153/cjm-1978-039-8 , S2CID  123812465
• Фомин, Ф.В .; Гасперс, С.; Саурабх, С. (2007), «Улучшенные точные алгоритмы подсчета 3- и 4-раскрасок», Труды 13-й ежегодной международной конференции COCOON 2007 , Lecture Notes in Computer Science , том 4598, Springer, стр. 65–74, doi : 10.1007/978-3-540-73545-8_9 , ISBN 978-3-540-73544-1
• Гэри, М. Р.; Джонсон , Д. С. (1979), Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5
• Гэри, М. Р.; Джонсон , Д. С .; Стокмейер, Л. (1974), «Некоторые упрощенные NP-полные задачи», Труды шестого ежегодного симпозиума ACM по теории вычислений, стр. 47–63, doi :10.1145/800119.803884, ISBN 9781450374231, S2CID  207693360
• Голдберг, Л. А.; Джеррум , М. (июль 2008 г.), «Неприближенность полинома Тутте», Information and Computation , 206 (7): 908–929, arXiv : cs/0605140 , doi : 10.1016/j.ic.2008.04.003, S2CID  53304001
• Голдберг, А. В .; Плоткин, С. А.; Шеннон, Г. Е. (1988), «Параллельное нарушение симметрии в разреженных графах», SIAM Journal on Discrete Mathematics , 1 (4): 434–446, doi :10.1137/0401044
• Халлдорссон, ММ (1993), «Еще лучшая гарантия производительности для приблизительной раскраски графов», Information Processing Letters , 45 : 19–23, doi :10.1016/0020-0190(93)90246-6
• Холиер, И. (1981), «NP-полнота раскраски рёбер», SIAM Journal on Computing , 10 (4): 718–720, doi :10.1137/0210055, S2CID  13131049
• Jaeger, F.; Vertigan, DL; Welsh, DJA (1990), "О вычислительной сложности полиномов Джонса и Тутта", Математические труды Кембриджского философского общества , 108 (1): 35–53, Bibcode : 1990MPCPS.108...35J, doi : 10.1017/S0305004100068936, S2CID  121454726
• Дженсен, ТР; Тофт, Б. (1995), Проблемы раскраски графов , Wiley-Interscience, Нью-Йорк, ISBN 0-471-02865-7
• Хуллер, Самир; Вазирани, Виджай В. (1991-09-30), «Раскраска планарного графа не является самоприводимой, предполагая, что P ≠ NP», Теоретическая информатика , 88 (1): 183–189, doi :10.1016/0304-3975(91)90081-C, ISSN  0304-3975
• Кнут, Дональд Эрвин (1997), Получисленные алгоритмы , Искусство программирования, т. 2 (3-е изд.), Reading/MA: Addison-Wesley, ISBN 0-201-89684-2
• Koivisto, Mikko (январь 2004 г.), Sum-Product Algorithms for the Analysis of Genetic Risks (диссертация на соискание ученой степени доктора философии), Dept. CS Ser. Pub. A, vol. A-2004-1, University of Helsinki, ISBN 952-10-1578-0
• Кубале, М. (2004), Раскраска графов , Американское математическое общество, ISBN 0-8218-3458-4
• Кун, Ф. (2009), «Слабая раскраска графов: распределенные алгоритмы и приложения», Труды 21-го симпозиума по параллелизму в алгоритмах и архитектурах , стр. 138–144, doi :10.1145/1583991.1584032, ISBN 978-1-60558-606-9, S2CID  8857534
• Лоулер, Э. Л. (1976), «Заметка о сложности проблемы хроматического числа», Information Processing Letters , 5 (3): 66–67, doi :10.1016/0020-0190(76)90065-X
• Лейт, DJ; Клиффорд, P. (2006), "Самоуправляемый распределенный алгоритм выбора канала для WLAN" (PDF) , Proc. RAWNET 2006, Бостон, MA , получено 03.03.2016
• Льюис, Р.М.Р. (2016), Руководство по раскраске графов: алгоритмы и приложения, Springer International Publishing, ISBN 978-3-319-25728-0
• Льюис, Р.М.Р. (2021), Руководство по раскраске графов, Тексты по информатике, doi : 10.1007/978-3-030-81054-2, ISBN 978-3-030-81053-5, S2CID  57188465
• Линиал, Н. (1992), «Локальность в алгоритмах распределенных графов», SIAM Journal on Computing , 21 (1): 193–201, CiteSeerX  10.1.1.471.6378 , doi : 10.1137/0221015
• ван Линт, Дж. Х.; Уилсон, Р. М. (2001), Курс комбинаторики (2-е изд.), Cambridge University Press, ISBN 0-521-80340-3
• Маркс, Даниэль (2004), «Проблемы раскраски графов и их применение в планировании», Periodica Polytechnica, Электротехника , т. 48, стр. 11–16, CiteSeerX  10.1.1.95.4268
• Мисельски, Дж. (1955), «Sur le coloriage desgraphes» (PDF) , Colloq. Математика. , 3 (2): 161–162, doi : 10,4064/см-3-2-161-162
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), "Теорема 3.13", Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Гейдельберг: Springer, стр. 42, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058
• Панконези, Алессандро; Рицци, Ромео (2001), «Некоторые простые распределенные алгоритмы для разреженных сетей» (PDF) , Распределенные вычисления , 14 (2), Берлин, Нью-Йорк: Springer-Verlag : 97–100, doi :10.1007/PL00008932, ISSN  0178-2770, S2CID  17661948
• Панконеси, А.; Шринивасан, А. (1996), «О сложности декомпозиции распределенной сети», Журнал алгоритмов , т. 20
• Pawlik, A.; Kozik, J.; Krawczyk, T.; Lasoń, M.; Micek, P.; Trotter, W.; Walczak, B. (2014), "Графы пересечений отрезков прямых без треугольников с большим хроматическим числом", Журнал комбинаторной теории , Серия B, 105 (5): 6–10, arXiv : 1209.1595 , doi : 10.1016/j.jctb.2013.11.001
• Скотт, Алекс; Сеймур, Пол (2020), «Обзор χ -ограниченности», Журнал теории графов , 95 (3): 2–3, doi :10.1002/jgt.22601, S2CID  4760027
• Секинэ, Кёко; Имаи, Хироши; Тани, Сейитиро (1995), «Вычисление полинома Тутте для графа умеренного размера», Труды 6-го Международного симпозиума по алгоритмам и вычислениям (ISAAC 1995) , Lecture Notes in Computer Science , т. 1004, Springer, стр. 224–233, doi :10.1007/BFb0015427, ISBN 3-540-60573-8
• Шнайдер, Йоханнес; Ваттенхофер, Роджер (2010), «Новый метод нарушения распределенной симметрии», в Richa, Andréa W .; Guerraoui, Rachid (ред.), Труды 29-го ежегодного симпозиума ACM по принципам распределенных вычислений, PODC 2010, Цюрих, Швейцария, 25–28 июля 2010 г. , Ассоциация вычислительной техники, стр. 257–266, doi :10.1145/1835698.1835760, ISBN 978-1-60558-888-9
• Шнайдер, Йоханнес; Ваттенхофер, Роджер (2008), «Распределенный логарифмически-звездный алгоритм максимального независимого множества для графов с ограниченным ростом», в Bazzi, Rida A.; Patt-Shamir, Boaz (ред.), Труды двадцать седьмого ежегодного симпозиума ACM по принципам распределенных вычислений, PODC 2008, Торонто, Канада, 18–21 августа 2008 г. , Ассоциация вычислительной техники, стр. 35–44, doi :10.1145/1400751.1400758, ISBN 978-1-59593-989-0
• Тутт, У. Т. (1949), «О вложении линейных графов в поверхности», Труды Лондонского математического общества , 2,51, стр. 474–483
• Тутт, В. Т. (1954), «Вклад в теорию хроматических многочленов», Канадский журнал математики , т. 6, стр. 80–91
• Уэлш, DJA; Пауэлл, MB (1967), «Верхняя граница хроматического числа графа и ее применение к задачам составления расписания», The Computer Journal , 10 (1): 85–86, doi : 10.1093/comjnl/10.1.85
• Уэст, ДБ (1996), Введение в теорию графов , Prentice-Hall, ISBN 0-13-227828-6
• Wilf, HS (1986), Алгоритмы и сложность , Prentice–Hall
• Врохна, М.; Живны, С. (2020), «Повышенная твёрдость для H-раскрасок G-раскрашиваемых графов», Труды тридцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 1426–1435
• Йейтс, Ф. (1937), Планирование и анализ факторных экспериментов (Техническое сообщение), т. 35, Харпенден, Англия: Бюро почв Содружества
• Чжан, Цунь-Цюань (1997), Целочисленные потоки и циклические покрытия графов , CRC Press, ISBN 978-0-8247-9790-4
• Замир, Ор (2021), «Преодоление барьера 2 ⁿ для 5- и 6-цветной раскраски», в Бансал, Никхил; Мерелли, Эмануэла; Уоррелл, Джеймс (ред.), 48-й Международный коллоквиум по автоматам, языкам и программированию (ICALP) , Международные труды Лейбница по информатике (LIPIcs), т. 198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 113:1–113:20, doi : 10.4230/LIPIcs.ICALP.2021.113
• Цукерман, Д. (2007), «Линейные экстракторы степени и неаппроксимируемость максимальной клики и хроматического числа», Теория вычислений , 3 : 103–128, doi : 10.4086/toc.2007.v003a006
• Зыков А. А. (1949), "О некоторых свойствах линейных комплексов", Матем. Сборник , Новая серия, 24 (66): 163–188, МР  0035428. Переведено на английский язык в Amer. Math. Soc. Translation , 1952, MR 0051516.

Внешние ссылки

• Высокопроизводительные алгоритмы раскраски графов. Набор из 8 различных алгоритмов (реализованных на языке C++), используемых в книге «Руководство по раскраске графов: алгоритмы и приложения» (Springer International Publishers, 2015).
• Раскраска графов Джозефа Калберсона (программы раскраски графов)
• CoLoRaTiOn Джима Эндрюса и Майка Феллоуза — это головоломка по раскрашиванию графов.
• Ссылки на исходные коды Graph Coloring Архивировано 04.07.2008 на Wayback Machine
• Код для эффективного вычисления полиномов Тутте, хроматических и потоковых полиномов. Архивировано 16 апреля 2008 г. на Wayback Machine Гэри Хаггардом, Дэвидом Дж. Пирсом и Гордоном Ройлом.
• Веб-приложение для раскраски графов от Хосе Антонио Мартина Х.