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

Не путать с раскраской Edge .

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

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

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

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

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

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

История

См. Также: История теоремы о четырех цветах и ​​История теории графов.

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

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

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

В 1912 году Джордж Дэвид Биркгоф ввел хроматический полином для изучения проблемы раскраски, который был обобщен на полином Тутта , У. Таттом оба из которых являются важными инвариантами в алгебраической теории графов . Кемпе уже обратил внимание на общий неплоский случай в 1879 году: и многие результаты по обобщению раскраски плоских графов на поверхности более высокого порядка были получены в начале 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 -раскрашиваемая имеют тот же смысл.

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

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

Основная статья: Хроматический полином

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

Доступные цвета	1	2	3	4	…
Количество раскрасок	0	0	12	72	…

Хроматический многочлен — это функция 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}.

Хроматические полиномы для некоторых графов

Треугольник К 3	т ( т – 1)( т – 2)
Полный граф K n	т ( т – 1)( т – 2) … ( т – ( п – 1))
Дерево с n вершинами	т ( т – 1) п – 1
Цикл C n	( т – 1) н + (-1) н ( т – 1)
график Петерсена	т ( т – 1)( т – 2)( т 7 - 12:00 6 + 67 т 5 – 230 т 4 + 529 т 3 – 814 ч. 2 + 775 т – 352)

Окраска края

Основная статья: Окраска краев

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

Тотальная раскраска

Основная статья: Тотальная раскраска

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

Окраска лица

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

Тутте

Для графа G с сильным вложением на ориентируемую поверхность Уильям Т. Тутт обнаружил, что если граф раскрашивается по k-граням, то G допускает нигде ненулевой k-поток. Эквивалентность имеет место, если поверхность является сферой.

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

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

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

Свойства

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

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

$1\leq \chi (G)\leq n.$

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

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

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

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

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

$\chi (G)\leq \Delta (G)+1.$

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

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

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

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

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

$\chi (G)\geq \omega (G).$

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

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

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

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

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

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

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

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

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

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

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

Графы с большим хроматическим числом

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

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

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

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

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

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

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

$\chi '(G)=\chi (L(G)).$

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

$\chi '(G)\geq \Delta (G).$

Более того,

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

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

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

Другая недвижимость

Граф имеет k -раскраску тогда и только тогда, когда он имеет ациклическую ориентацию , для которой самого длинного пути длина не превышает k ; это теорема Галлаи-Хассе-Роя-Витавера ( Нешетржил и Оссона де Мендес, 2012 ).

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

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

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

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

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

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

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

Алгоритмы

Раскраска графа
Решение
Имя	Раскраска графа, раскраска вершин, k -раскраска
Вход	Граф G с n вершинами. Целое число k
Выход	Допускает ли G правильную раскраску вершин в k цветов?
Время работы	О(2  н п )
Сложность	NP-полный
Сокращение с	3-Выполнимость
Гэри-Джонсон	GT4
Оптимизация
Имя	Хроматическое число
Вход	Граф G с n вершинами.
Выход	х( г )
Сложность	NP-жесткий
Аппроксимируемость	О( n (логарифм n ) −3 (журнал журнал n ) 2 )
Неприближаемость	На ​ 1-е ), если только P = NP
Задача подсчета
Имя	Хроматический полином
Вход	Граф G с n вершинами. Целое число k
Выход	Число P ( G , k ) собственных k -раскрасок G
Время работы	О(2  н п )
Сложность	#P-полное
Аппроксимируемость	FPRAS для ограниченных случаев
Неприближаемость	Нет PTAS , если P = NP

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

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

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

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

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

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

Сокращение

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

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

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

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

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

$P(G-uv,k)=P(G/uv,k)+P(G,k)$

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

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

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

Основная статья: Жадная раскраска

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычислительная сложность

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

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

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

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

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

Приложения

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

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

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

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

Основная статья: Распределение регистров

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

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

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

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

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

Теория Рэмси

Основная статья: теория Рэмси

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

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

Общая раскраска с различением соседних вершин

Полная раскраска с дополнительным ограничением: любые две соседние вершины имеют разные наборы цветов.

Ациклическая окраска

Любой 2-хроматический подграф ацикличен.

B-раскраска

раскраска вершин, при которой каждый цветовой класс содержит вершину, имеющую соседа во всех других цветовых классах.

Круговая раскраска

Мотивированы системами задач, в которых производство происходит циклично.

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

Неправильная раскраска вершин, при которой каждый цветовой класс порождает независимое множество или клику.

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

Каждая пара цветов появляется хотя бы на одном краю.

Дефектная окраска

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

Отличительная окраска

Неправильная раскраска вершин, разрушающая всю симметрию графа.

Справедливая окраска

Размеры цветовых классов отличаются не более чем на один

Точная окраска

Каждая пара цветов появляется ровно на одном краю.

Дробная окраска

Вершины могут иметь несколько цветов, и на каждом ребре сумма цветных частей каждой вершины не превышает единицы.

Гамильтонова раскраска

Использует длину самого длинного пути между двумя вершинами, также известную как расстояние обхода.

Гармоничная окраска

Каждая пара цветов появляется не более чем на одном краю.

Раскраска заболеваемости

Каждое соседнее попадание вершины и ребра окрашено в разные цвета.

Унаследованная окраска вершин

Набор раскрасок вершин, индуцированных идеальными сопоставлениями графов Graph, окрашенных в цвета ребер .

Окраска границ интервала

Цвет ребер, сходящихся в общей вершине, должен быть смежным.

Раскраска списка

Каждая вершина выбирает из списка цветов

Раскраска краев списка

Каждое ребро выбирает из списка цветов

L(h, k)-раскраска

Разница цветов соседних вершин не менее h , а разница цветов вершин на расстоянии два не менее k . Частным случаем является L(2,1)-раскраска .

Ориентированная раскраска

Учитывает ориентацию ребер графа.

Раскраска пути

Моделирует проблему маршрутизации в графах

Радио раскраска

Сумма расстояний между вершинами и разницы их цветов больше k+1, где k — целое положительное число.

Раскраска рангов

Если две вершины имеют одинаковый цвет i , то каждый путь между ними содержит вершину с цветом больше i.

Подкраска

Неправильная раскраска вершин, при которой каждый цветовой класс порождает объединение клик.

Суммарная раскраска

Критерий минимизации — сумма цветов

Звездная раскраска

Каждый 2-хроматический подграф представляет собой непересекающуюся совокупность звезд.

Сильная окраска

Каждый цвет появляется в каждом разделе одинакового размера ровно один раз.

Яркая окраска краев

Ребра раскрашены так, что каждый цветовой класс вызывает сопоставление (эквивалентно раскраске квадрата линейного графа).

Т-раскраска

Абсолютное значение разницы между двумя цветами соседних вершин не должно принадлежать фиксированному множеству T.

Тотальная окраска

Вершины и ребра окрашены в цвет.

Центрированная раскраска

Каждый связный индуцированный подграф имеет цвет, который используется ровно один раз.

Окраска кромок без треугольников

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

Слабая окраска

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

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

См. также

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

Ссылки

• Баренбойм, Л.; Элкин, М. (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), «Новые методы раскраски вершин графа», Communications of the ACM , 22 (4): 251–256, doi : 10.1145/359094.359101 , S2CID   14838769
• Брукс, Р.Л. (1941), «О раскраске узлов сети», Труды Кембриджского философского общества , 37 (2): 194–197, Бибкод : 1941PCPS...37..194B , doi : 10.1017/S030500410002168X , S2CID   209835194
• де Брёйн, Нью-Йорк ; Эрдеш, П. (1951), «Проблема цвета бесконечных графов и проблема теории отношений» (PDF) , Nederl. Акад. Ветенш. Учеб. Сер. A , 54 : 371–373, doi : 10.1016/S1385-7258(51)50053-7 , заархивировано из оригинала (PDF) 10 марта 2016 г. , получено 16 мая 2009 г. (= Indag. Math. 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. Симпозиум SIGPLAN 1982 года по созданию компиляторов , стр. 98–105, doi : 10.1145/800230.806984 , ISBN  0-89791-074-5 , S2CID   16872867
• Коул, Р.; Вишкин, У. (1986), «Детерминистическое подбрасывание монеты с применением оптимального ранжирования параллельных списков», Information and Control , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7
• Кормен, TH; Лейзерсон, CE; Ривест, Р.Л. (1990), Введение в алгоритмы (1-е изд.), The MIT Press.
• Крещенци, П.; Канн, В. (декабрь 1998 г.), «Как найти результаты наилучшего приближения - продолжение Гари и Джонсона», ACM SIGACT News , 29 (4): 90, doi : 10.1145/306198.306210 , S2CID   15748200
• Дейли, Д. П. (1980), «Единственность раскраски и раскрашиваемость плоских 4-регулярных графов NP-полны», Discrete Mathematics , 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), «Теория графов и вероятность», Canadian Journal of Mathematics , 11 : 34–38, doi : 10.4153/CJM-1959-003-9 , S2CID   122784453
• Фосетт, Б.В. (1978), «О бесконечных полных раскрасках графов», кан. Дж. Математика. , 30 (3): 455–457, doi : 10.4153/cjm-1978-039-8 , S2CID   123812465
• Фомин Ф.В. ; Гасперс, С.; Саураб, С. (2007), «Улучшенные точные алгоритмы подсчета 3- и 4-раскрасок», Proc. 13-я ежегодная международная конференция COCOON 2007 , Конспекты лекций по информатике , том. 4598, Springer, стр. 65–74, номер документа : 10.1007/978-3-540-73545-8_9 , ISBN.  978-3-540-73544-1
• Гэри, MR ; Джонсон, Д.С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN  0-7167-1045-5
• Гэри, MR ; Джонсон, Д.С .; Стокмейер, Л. (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
• Гольдберг, А.В. ; Плоткин, С.А.; Шеннон, GE (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
• Джагер, Ф.; Вертиган, ДЛ; Уэлш, DJA (1990), «О вычислительной сложности полиномов Джонса и Тутта», Mathematical Proceedings of the Cambridge Philosophical Society , 108 (1): 35–53, Bibcode : 1990MPCPS.108...35J , doi : 10.1017 /S0305004100068936 , S2CID   121454726
• Дженсен, ТР; Тофт, Б. (1995), Проблемы раскраски графов , Wiley-Interscience, Нью-Йорк, ISBN  0-471-02865-7
• Хуллер, Самир; Вазирани, Виджай В. (30 сентября 1991 г.), «Раскраска плоских графов не является самосократимой, если предположить, что P ≠ NP» , Theoretical Computer Science , 88 (1): 183–189, doi : 10.1016/0304-3975( 91)90081-С , ISSN   0304-3975
• Кнут, Дональд Эрвин (1997), Получисловые алгоритмы , Искусство компьютерного программирования, том. 2 (3-е изд.), Ридинг/Массачусетс: Аддисон-Уэсли, ISBN  0-201-89684-2
• Койвисто, Микко (январь 2004 г.), Алгоритмы суммы произведений для анализа генетических рисков (докторская диссертация), Серия кафедры CS. Паб. А, том. A-2004-1, Хельсинкский университет, 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
• Лейт, диджей; Клиффорд, П. (2006), «Самоуправляемый алгоритм выбора распределенного канала для WLAN» (PDF) , Proc. RAWNET 2006, Бостон, Массачусетс , получено 3 марта 2016 г.
• Льюис, RMR (2016), Руководство по раскраске графов: алгоритмы и приложения , Springer International Publishing, ISBN  978-3-319-25728-0
• Льюис, RMR (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, Electrical Engineering , vol. 48, стр. 11–16, CiteSeerX   10.1.1.95.4268.
• Мисельски, Дж. (1955), «О раскраске графов» (PDF) , Colloq. Математика. , 3 (2): 161–162, doi : 10,4064/см-3-2-161-162 .
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, с. 42, номер домена : 10.1007/978-3-642-27875-4 , ISBN  978-3-642-27874-7 , МР   2920058 .
• Панконези, Алессандро; Рицци, Ромео (2001), «Некоторые простые распределенные алгоритмы для разреженных сетей» (PDF) , Distributed Computing , 14 (2), Берлин, Нью-Йорк: Springer-Verlag : 97–100, doi : 10.1007/PL00008932 , ISSN   0178- 2770 , S2CID   17661948
• Панконези, А.; Шринивасан, А. (1996), «О сложности декомпозиции распределенной сети», Journal of Algorithms , vol. 20
• Павлик, А.; Козик Дж.; Кравчик, Т.; Ласонь, М.; Мичек, П.; Троттер, В.; Вальчак, Б. (2014), «Графы пересечений отрезков прямых с большим хроматическим числом без треугольников», Журнал комбинаторной теории , серия B, 105 (5): 6–10, arXiv : 1209.1595 , doi : 10.1016/j. jctb.2013.11.001
• Скотт, Алекс; Сеймур, Пол (2020), «Обзор χ -ограниченности», Journal of Graph Theory , 95 (3): 2–3, doi : 10.1002/jgt.22601 , S2CID   4760027
• Секине, Кёко; Имаи, Хироши; Тани, Сейичиро (1995), «Вычисление полинома Тутте для графа среднего размера», Proc. 6-й Международный симпозиум по алгоритмам и вычислениям (ISAAC, 1995) , Конспекты лекций по информатике , том. 1004, Springer, стр. 224–233, doi : 10.1007/BFb0015427 , ISBN.  3-540-60573-8
• Шнайдер, Йоханнес; Ваттенхофер, Роджер (2010), «Новый метод нарушения распределенной симметрии», Рича, Андреа В .; Геррауи, Рашид (ред.), Труды 29-го ежегодного симпозиума ACM по принципам распределенных вычислений, PODC 2010, Цюрих, Швейцария, 25–28 июля 2010 г. , Ассоциация вычислительной техники, стр. 257–266, doi : 10.1145/ 1835698.1835760 , ISBN  978-1-60558-888-9
• Шнайдер, Йоханнес; Ваттенхофер, Роджер (2008), «Алгоритм максимального независимого множества с лог-звездным распределением для графов с ограниченным ростом», в Баззи, Рида А.; Патт-Шамир, Боаз (ред.), Труды двадцать седьмого ежегодного симпозиума ACM по принципам распределенных вычислений, PODC 2008, Торонто, Канада, 18–21 августа 2008 г. , Ассоциация вычислительной техники, стр. 35–44, дои : 10.1145/1400751.1400758 , ISBN  978-1-59593-989-0
• Тутте, В.Т. (1949), "О вложении линейных графов в поверхности", Proc. Лондонская математика. Соц. , 2,51, стр. 474–483.
• Тутте, В.Т. (1954), «Вклад в теорию хроматического полинома», Канада. Дж. Математика. , том. 6, стр. 80–91.
• валлийский, DJA; Пауэлл, МБ (1967), «Верхняя граница хроматического числа графа и ее применение к задачам составления расписания», The Computer Journal , 10 (1): 85–86, doi : 10.1093/comjnl/10.1.85
• Уэст, Д.Б. (1996), Введение в теорию графов , Прентис-Холл, ISBN  0-13-227828-6
• Уилф, HS (1986), Алгоритмы и сложность , Прентис-Холл
• Вречная, М.; Живны, С. (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, номер документа : 10.4230/LIPIcs.ICALP.2021.113.
• Цукерман, Д. (2007), «Экстракторы линейных степеней и неаппроксимируемость максимальной клики и хроматического числа», Theory of Computing , 3 : 103–128, doi : 10.4086/toc.2007.v003a006
• Zykov, A. A. (1949), "О некоторых свойствах линейных комплексов" [On some properties of linear complexes], Mat. Sbornik , New Series (in Russian), 24 (66): 163–188, MR  0035428 . Translated into English in Amer. Math. Soc. Translation , 1952, MR 0051516 .

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

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