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

Методика присвоения цветов элементам графика

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

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

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

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

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

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

История

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

Первые результаты о раскраске графов касаются почти исключительно плоских графов в форме раскраски карт . Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри постулировал гипотезу четырех цветов , отметив, что четырех цветов было достаточно, чтобы раскрасить карту так, чтобы ни один регион, имеющий общую границу, не получил один и тот же цвет. Брат Гатри передал этот вопрос своему учителю математики Огастесу Де Моргану в Университетском колледже , который упомянул его в письме Уильяму Гамильтону в 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 -раскрашиваемая имеют тот же смысл.

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

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

Хроматический полином подсчитывает количество способов раскрасить граф, используя некоторые из заданного количества цветов. Например, используя три цвета, график на соседнем изображении можно раскрасить 12 способами. Имея только два цвета, его вообще невозможно раскрасить. Имея четыре цвета, его можно раскрасить 24 + 4⋅12 = 72 способами: если использовать все четыре цвета, то получится 4! = 24 допустимых раскраски ( каждое присвоение четырех цветов любому четырехвершинному графу является правильной раскраской); и для каждого выбора трех из четырех цветов существует 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 ) . Раскраска Тейта — это трёхрёберная раскраска кубического графа . Теорема о четырех цветах эквивалентна утверждению, что каждый планарный кубический граф без мостов допускает раскраску Тейта.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Полные графы имеют и , а нечетные циклы имеют и , поэтому для этих графов эта оценка является наилучшей. Во всех остальных случаях оценку можно немного улучшить; Теорема Брукса ^[4] утверждает, что ${\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-хроматического графа без треугольника, и этот пример можно обобщить на мицельскианы .

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

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

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

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

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

Реберная раскраска 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 ; это теорема Галлаи-Хассе-Роя-Витавера (Нешетржил и Оссона де Мендес, 2012).

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

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

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

Алгоритмы

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

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

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

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

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

Используя динамическое программирование и ограничение числа максимальных независимых множеств , можно определить k -раскраску во времени и пространстве . ^[10] Используя принцип включения-исключения и алгоритм Йейтса для быстрого дзета-преобразования, k -раскраску можно определить за время ^{[9] [11] [12] [13]} для любого k . Известны более быстрые алгоритмы для 3- и 4-раскраски, которые можно решить за время ^[14] и , ^[15] соответственно. Экспоненциально более быстрые алгоритмы также известны для 5- и 6-раскраски, а также для ограниченных семейств графов, включая разреженные графы. ^[16] ${\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 ребер. ^[17] Анализ можно улучшить с точностью до полиномиального коэффициента количества остовных деревьев входного графа. ^[18] На практике стратегии ветвей и границ и отказ от изоморфизма графов используются, чтобы избежать некоторых рекурсивных вызовов. Время выполнения зависит от эвристики, используемой для выбора пары вершин. ${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$ ${\displaystyle t(G)}$

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

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

Жадный алгоритм рассматривает вершины в определенном порядке ,… и назначает наименьший доступный цвет, не используемый соседями вершины среди ,…, , добавляя при необходимости новый цвет. Качество полученной окраски зависит от выбранного порядка. Существует упорядочение, приводящее к жадной раскраске с оптимальным количеством цветов. С другой стороны, жадные раскраски могут быть сколь угодно плохими; например, граф короны на n вершинах может быть двухцветным, но имеет порядок, приводящий к жадной раскраске цветами. ${\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-трудно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

Теория Рэмси

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

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

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

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

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

Примечания

1. М. Кубале, История раскраски графов , в Кубале (2004).
2. ван Линт и Уилсон (2001), гл. 33.
3. Дженсен и Тофт (1995), с. 2.
4. Брукс (1941).
5. Декарт (1947).
6. Скотт и Сеймур (2020).
7. Павлик и др. (2014).
8. Эрдеш (1959).
9. Бьорклунд, Хусфельдт и Койвисто (2009), стр. 550.
10. Лоулер (1976).
11. Йейтс (1937), с. 66-67.
12. Кнут (1997), Глава 4.6.4, стр. 501-502.
13. Койвисто (2004), стр. 45, 96–103.
14. Бейгель и Эппштейн (2005).
15. Фомин, Гасперс и Саураб (2007).
16. Замир (2021).
17. Уилф (1986).
18. Секине, Имаи и Тани (1995).
19. Уэлш и Пауэлл (1967).
20. Брелаз (1979).
21. Льюис (2021).
22. Шнайдер и Ваттенхофер (2010).
23. Коул и Вишкин (1986), см. также Кормен, Лейзерсон и Ривест (1990, раздел 30.5).
24. Голдберг, Плоткин и Шеннон (1988).
25. Шнайдер и Ваттенхофер (2008).
26. Баренбойм и Элкин (2009); Кун (2009).
27. Например, см. Лейт и Клиффорд (2006) и Даффи, О'Коннелл и Сапожников (2008).
28. Гари, Джонсон и Стокмейер (1974); Гэри и Джонсон (1979).
29. Дейли (1980).
30. Хуллер и Вазирани (1991).
31. Халлдорссон (1993).
32. Цукерман (2007).
33. Булин, Крохин и Опршал (2019).
34. Врочна и Живной (2020).
35. Джагер, Вертиган и Уэлш (1990).
36. Голдберг и Джеррум (2008).
37. Холиер (1981).
38. Крещенци и Канн (1998).
39. Маркс (2004).
40. Чайтин (1982).
41. Льюис (2021), стр. 221–246, Глава 8: Разработка спортивных лиг.
42. Льюис (2021), стр. 203–220, Глава 7: Разработка планов рассадки.
43. Льюис (2021), стр. 247–276, Глава 9: Составление расписания университетов.
44. Льюис (2021), стр. 5–6, Раздел 1.1.3: Планирование такси.
45. Льюис (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), «Новые методы раскраски вершин графа», 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 г.(= Индиг. Матем. 13 )
• Булин, Дж.; Крохин А.; Опршал, Дж. (2019), «Алгебраический подход к удовлетворению ограничений обещаний», Труды 51-го ежегодного симпозиума ACM SIGACT по теории вычислений , стр. 602–613, arXiv : 1811.00970 , doi : 10.1145/3313276.3316300
• Берлинг, Джеймс Перкинс (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, Бибкод : 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), Руководство по раскраске графов, Тексты по информатике, номер документа : 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), «Sur le coloriage desgraphes» (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) , Распределенные вычисления , Берлин, Нью-Йорк: Springer-Verlag , 14 (2): 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, номер документа : 10.1007/BFb0015427, ISBN. 3-540-60573-8
• Шнайдер, Йоханнес; Ваттенхофер, Роджер (2010), «Новый метод нарушения распределенной симметрии», Рича , Андреа В .; Геррауи, Рашид (ред.), Труды 29-го ежегодного симпозиума ACM по принципам распределенных вычислений, PODC 2010, Цюрих, Швейцария, 25–28 июля 2010 г. , Ассоциация вычислительной техники, стр. 257–266, doi : 10.1145/ 1835698.1835760
• Шнайдер, Йоханнес; Ваттенхофер, Роджер (2008), «Алгоритм максимального независимого множества с лог-звездным распределением для графов с ограниченным ростом», в Баззи, Рида А.; Патт-Шамир, Боаз (ред.), Труды двадцать седьмого ежегодного симпозиума ACM по принципам распределенных вычислений, PODC 2008, Торонто, Канада, 18–21 августа 2008 г., Ассоциация вычислительной техники, стр. 35–44, дои : 10.1145/1400751.1400758
• валлийский, 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, Харпенден, Англия: Бюро почв Содружества.
• Замир Ор (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), «Экстракторы линейных степеней и неаппроксимируемость макс. клики и хроматического числа», Theory of Computing , 3 : 103–128, doi : 10.4086/toc.2007.v003a006
• Зыков А. А. (1949), "О некоторых свойствах линейных комплексов", Матем. Сборник , Новая серия, 24 (66): 163–188, МР  0035428. Переведен на английский амер. Математика. Соц. Перевод , 1952, МР 0051516.

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

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