Жадная раскраска - Greedy coloring

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

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

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

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

Алгоритм

Жадную раскраску для данного порядка вершин можно вычислить с помощью алгоритм что работает в линейное время. Алгоритм обрабатывает вершины в заданном порядке, присваивая каждой из них цвет по мере ее обработки. Цвета могут быть представлены числами ${displaystyle 0,1,2,dots }$ и каждой вершине дается цвет с наименьшее число, которое еще не использовалось одним из его соседей. Чтобы найти наименьший доступный цвет, можно использовать массив для подсчета количества соседей каждого цвета (или, альтернативно, для представления набора цветов соседей), а затем сканировать массив, чтобы найти индекс своего первого нуля.^[2]

В Python, алгоритм можно выразить как:

def first_available(color_list):    "" "Вернуть наименьшее неотрицательное целое число, не входящее в указанный список цветов." ""    color_set = набор(color_list)    считать = 0    пока Истинный:        если считать нет в color_set:            возвращаться считать        считать += 1        def greedy_color(грамм, порядок):    "" "Найдите жадную раскраску G в указанном порядке.    Предполагается, что представление G похоже на https://www.python.org/doc/essays/graphs/    в разрешении перебора соседей узла / вершины с помощью «for w in G [node]».    Возвращаемое значение - словарь, отображающий вершины в их цвета. "" "    цвет = диктовать()    за узел в порядок:        used_neighbour_colors = [цвет[номер] за номер в грамм[узел]                                 если номер в цвет]        цвет[узел] = first_available(used_neighbour_colors)    возвращаться цвет

В first_available подпрограмма занимает время, пропорциональное длине ее списка аргументов, потому что она выполняет два цикла: один по самому списку, а другой по списку счетчиков одинаковой длины. Время выполнения общего алгоритма раскраски определяется вызовами этой подпрограммы. Каждое ребро в графе вносит свой вклад только в один из этих вызовов, один для конечной точки ребра, который находится позже в порядке вершин. Следовательно, сумма длин аргументов приводит к first_available, и общее время алгоритма пропорциональны количеству ребер в графе.^[2]

Альтернативный алгоритм, производящий такую ​​же окраску,^[3] состоит в том, чтобы выбрать наборы вершин каждого цвета, по одному цвету за раз. В этом методе каждый цветовой класс ${displaystyle C}$ выбирается сканированием вершин в заданном порядке. Когда это сканирование обнаруживает неокрашенную вершину ${displaystyle v}$ у которого нет соседа ${displaystyle C}$, он добавляет ${displaystyle v}$ к ${displaystyle C}$. Таким образом, ${displaystyle C}$ становится максимальное независимое множество среди вершин, которым еще не были присвоены меньшие цвета. Таким образом алгоритм неоднократно находит классы цветов, пока не будут окрашены все вершины. Однако он включает в себя несколько сканирований графика, по одному сканированию для каждого цветового класса, вместо описанного выше метода, который использует только одно сканирование.^[4]

Выбор заказа

Различный порядок вершин графа может привести к тому, что жадная раскраска будет использовать разное количество цветов, от оптимального количества цветов до, в некоторых случаях, количества цветов, которое пропорционально количеству вершин в графе. например, граф короны (граф, составленный из двух непересекающиеся множества из п/2 вершины {а₁, а₂, ...} и {б₁, б₂, ...} путем подключения а_я к б_j в любое время я ≠ j) может быть особенно плохим случаем для жадной окраски. С порядком вершин а₁, б₁, а₂, б₂, ..., жадная раскраска будет использовать п/2 цвета, по одному цвету для каждой пары (а_я, б_я). Однако оптимальное количество цветов для этого графа - два, один цвет для вершин а_я и еще один для вершин б_я.^[5] Также существуют графы, в которых с большой вероятностью случайный порядок вершин приводит к количеству цветов, намного превышающему минимальный.^[6] Следовательно, при жадной раскраске важно тщательно выбирать порядок вершин.

Хорошие заказы

Вершины любого графа всегда можно упорядочить так, чтобы жадный алгоритм давал оптимальную раскраску. Ведь при любой оптимальной раскраске можно упорядочить вершины по цвету. Затем, когда кто-то использует жадный алгоритм с этим порядком, результирующая окраска автоматически становится оптимальной.^[7] Однако, поскольку оптимальная раскраска графа НП-полный, любая подзадача, которая позволила бы быстро решить эту проблему, включая поиск оптимального порядка для жадной окраски, является NP-жесткий.^[8]

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

Более того, любой идеальный порядок исключения наследственно оптимальный, что означает, что он оптимален как для самого графа, так и для всех его индуцированные подграфы. В идеально упорядочиваемые графики (который включает в себя хордовые графы, графики сопоставимости, и дистанционно-наследственные графы ) определяются как графы, имеющие наследственно оптимальный порядок.^[10] Распознавание идеально упорядочиваемых графов также является NP-полным.^[11]

Плохие заказы

Основная статья: Гранди номер

Количество цветов, полученных в результате жадной раскраски для наихудшего порядка данного графа, называется его Гранди номер.^[12]Как трудно найти хороший порядок вершин для жадной раскраски, так и найти плохой порядок вершин. Это NP-полное определение для данного графа грамм и номер k, существует ли упорядоченность вершин грамм что заставляет жадный алгоритм использовать k или больше цветов. В частности, это означает, что трудно найти худший заказ для грамм.^[12]

Графики, для которых порядок не важен

Основная статья: Хорошо раскрашенный график

В хорошо раскрашенные графики - графы, для которых все раскраски вершин дают одинаковое количество цветов. Это количество цветов на этих графиках равно как хроматическому числу, так и числу Гранди.^[12] Они включают кографы, а именно графы, в которых все индуцированные подграфы хорошо окрашены.^[13] Однако это совместно NP-полный чтобы определить, хорошо ли раскрашен график.^[12]

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

Вырождение

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

Поскольку трудно найти оптимальный порядок вершин, использовались эвристики, которые пытаются уменьшить количество цветов, не гарантируя при этом оптимальное количество цветов. Обычно для жадной раскраски используется порядок выбора вершины v минимум степень, закажите подграф с v удаленный рекурсивно, а затем поместите v последний в заказе. Наибольшая степень удаленной вершины, с которой сталкивается этот алгоритм, называется вырождение графа, обозначенный d. В контексте жадной раскраски та же самая стратегия упорядочивания также называется наименьшим последним упорядочением.^[14] Этот порядок вершин и вырождение можно вычислить за линейное время.^[15]Его можно рассматривать как улучшенную версию более раннего метода упорядочения вершин, упорядочения по наибольшему первому, который сортирует вершины в порядке убывания их степеней.^[16]

С упорядочиванием вырождения жадная раскраска будет использовать не более d + 1 цвета. Это потому, что при раскрашивании каждая вершина будет иметь не более d уже окрашенные соседи, поэтому одни из первых d + 1 цвета будут бесплатными для его использования.^[17] Жадная раскраска с упорядочением вырождения позволяет находить оптимальные раскраски для определенных классов графов, включая деревья, псевдолеса, и графы короны.^[18] Маркосян, Гаспарян и Рид (1996) определить график ${displaystyle G}$ быть ${displaystyle eta }$-совершенно, если для ${displaystyle G}$ и каждый индуцированный подграф из ${displaystyle G}$, хроматическое число равно вырождению плюс один. Для этих графов всегда оптимален жадный алгоритм с упорядочением по вырождению.^[19]Каждый ${displaystyle eta }$-совершенный граф должен быть граф без четных дырок, поскольку четные циклы имеют хроматическое число два и вырождение два, что не соответствует равенству в определении ${displaystyle eta }$-совершенные графики. Если граф и его дополнительный граф оба без четных отверстий, они оба ${displaystyle eta }$-идеально. Графики, которые являются идеальные графики и ${displaystyle eta }$-совершенные графы - это в точности хордовые графы. В более общем случае на графах без четных дырок упорядочение по вырожденности приближает оптимальную раскраску с точностью не более чем вдвое большего оптимального числа цветов; то есть его коэффициент аппроксимации равно 2.^[20] На графы единичного диска его коэффициент аппроксимации равен 3.^[21] В треугольная призма - наименьший граф, для которого один из порядков вырождения приводит к неоптимальной раскраске, а квадратная антипризма - наименьший граф, который нельзя оптимально раскрасить с помощью любого из его порядков вырождения.^[18]

Адаптивные заказы

Brélaz (1979) предлагает стратегию, называемую DSatur, для упорядочивания вершин в жадной раскраске, которая чередует построение упорядочения с процессом раскраски. В его версии алгоритма жадной раскраски следующая вершина, которую нужно раскрасить на каждом шаге, выбирается как вершина с наибольшим количеством различных цветов в ее район. В случае ничьей из связанных вершин выбирается вершина максимальной степени в подграфе неокрашенных вершин. Отслеживая наборы соседних цветов и их мощности на каждом шаге можно реализовать этот метод за линейное время.^[22]

Этим методом можно подобрать оптимальные раскраски для двудольные графы,^[23] все кактус графики, все колесные графики, все графы не более чем на шести вершинах, и почти каждый ${displaystyle k}$-раскрашиваемый граф.^[24] Несмотря на то что Левек и Маффре (2005) изначально утверждалось, что этот метод находит оптимальные цвета для Графики Мейниеля, позже они нашли контрпример этому утверждению.^[25]

Альтернативные схемы выбора цвета

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

Выбор онлайн

Альтернативные стратегии выбора цвета изучались в рамках онлайн-алгоритмы. В задаче онлайн-раскраски графа вершины графа предоставляются алгоритму раскраски по одной в произвольном порядке; алгоритм должен выбрать цвет для каждой вершины, основываясь только на цветах и ​​смежности между уже обработанными вершинами. В этом контексте качество стратегии выбора цвета оценивается по конкурентное соотношение, соотношение между количеством используемых цветов и оптимальным количеством цветов для данного графика.^[26]

Если не заданы дополнительные ограничения на графике, оптимальное соотношение конкуренции лишь слегка сублинейно.^[27] Однако для интервальные графики, возможно постоянное конкурентное соотношение,^[28] в то время как для двудольные графы и разреженные графики может быть достигнуто логарифмическое соотношение. В самом деле, для разреженных графов стандартная стратегия жадного раскраски, заключающаяся в выборе первого доступного цвета, обеспечивает это конкурентное соотношение, и можно доказать соответствие нижней границы конкурентного отношения любого онлайн-алгоритма раскраски.^[26]

Экономная окраска

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

Приложения

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

В комбинаторная теория игр, для беспристрастная игра дано в явном виде как ориентированный ациклический граф чьи вершины представляют игровые позиции, а чьи края представляют собой допустимые переходы из одной позиции в другую, алгоритм жадной раскраски (с использованием обратной стороны топологический порядок графика) вычисляет ним-стоимость каждой позиции. Эти значения могут использоваться для определения оптимальной игры в любой отдельной игре или в любом дизъюнктивная сумма игр.^[32]

Для графика максимальной степени Δ, любая жадная окраска будет использовать не более Δ + 1 цвета. Теорема Брукса заявляет, что с двумя исключениями (клики и нечетные циклы ) в большинстве Δ нужны цвета. Одно из доказательств теоремы Брукса включает нахождение порядка вершин, при котором первые две вершины смежны с последней вершиной, но не смежны друг с другом, и каждая вершина, кроме последней, имеет по крайней мере одного более позднего соседа. Для упорядочивания с этим свойством алгоритм жадной раскраски использует не более Δ цвета.^[33]

Примечания

1. Митчем (1976).
2. Хоанг и Шритаран (2016), Теорема 28.33, с. 738; Хусфельдт (2015), Алгоритм G
3. Frieze & McDiarmid (1997).
4. Валлийский и Пауэлл (1967).
5. Джонсон (1974); Хусфельдт (2015).
6. Кучера (1991); Хусфельдт (2015).
7. Хусфельдт (2015).
8. Маффрей (2003).
9. Роза, Люкер и Тарджан (1976).
10. Chvátal (1984); Хусфельдт (2015).
11. Миддендорф и Пфайффер (1990).
12. Закер (2006).
13. Кристен и Селков (1979).
14. Митчем (1976); Хусфельдт (2015).
15. Матула и Бек (1983).
16. Валлийский и Пауэлл (1967); Хусфельдт (2015).
17. Матула (1968); Секерес и Вильф (1968).
18. Косовский и Манушевский (2004).
19. Маркосян, Гаспарян и Рид (1996); Маффрей (2003).
20. Маркосян, Гаспарян и Рид (1996).
21. Греф, Штумпф и Вайсенфельс (1998).
22. Brélaz (1979); Левек и Маффре (2005).
23. Brélaz (1979).
24. Janczewski et al. (2001).
25. Левек и Маффре (2005).
26. Иранский (1994).
27. Ловас, Сакс и Троттер (1989); Вишванатан (1992).
28. Кирстед и Троттер (1981).
29. Симмонс (1982); Erdős et al. (1987).
30. Полетто и Саркар (1999). Хотя Полетто и Саркар описывают свой метод распределения регистров как не основанный на раскраске графов, он похож на жадную раскраску.
31. Перейра и Палсберг (2005).
32. Например, см. Раздел 1.1. Ниващ (2006).
33. Ловас (1975).

Рекомендации

• Brélaz, Daniel (апрель 1979 г.), «Новые методы окраски вершин графа», Коммуникации ACM, 22 (4): 251–256, Дои:10.1145/359094.359101
• Кристен, Клод А .; Сельков, Стэнли М. (1979), "Некоторые свойства совершенной окраски графов", Журнал комбинаторной теории, Серия B, 27 (1): 49–59, Дои:10.1016/0095-8956(79)90067-4, МИСТЕР  0539075
• Хваталь, Вацлав (1984), «Идеально упорядочиваемые графы», в Берже, Клод; Хваталь, Вацлав (ред.), Темы в Perfect Graphs, Анналы дискретной математики, 21, Амстердам: Северная Голландия, стр. 63–68.. Как цитирует Маффрей (2003).
• Эрдеш, П.; Hare, W. R .; Hedetniemi, S.T .; Ласкар, Р. (1987), «О равенстве Гранди и охроматических чисел графа» (PDF), Журнал теории графов, 11 (2): 157–159, Дои:10.1002 / jgt.3190110205, МИСТЕР  0889347.
• Фриз, Алан; МакДиармид, Колин (1997), "Алгоритмическая теория случайных графов", Случайные структуры и алгоритмы, 10 (1–2): 5–42, Дои:10.1002 / (SICI) 1098-2418 (199701/03) 10: 1/2 <5 :: AID-RSA2> 3.3.CO; 2-6, МИСТЕР  1611517.
• Gräf, A .; Штумпф, М .; Weißenfels, G. (1998), "О раскраске графов единичных дисков", Алгоритмика, 20 (3): 277–293, Дои:10.1007 / PL00009196, МИСТЕР  1489033.
• Hoàng, Chinh T .; Шритаран, Р. (2016), «Глава 28. Совершенные графы», в Туласираман, Кришнайян; Арумугам, субраманианский; Брандштадт, Андреас; Нишизэки, Такао (ред.), Справочник по теории графов, комбинаторной оптимизации и алгоритмам, Chapman & Hall / CRC Computer and Information Science Series, 34, CRC Press, стр. 707–750, ISBN  9781420011074.
• Husfeldt, Thore (2015), «Алгоритмы раскраски графов», в Beineke, Lowell W .; Уилсон, Робин Дж. (ред.), Темы теории хроматических графов, Энциклопедия математики и ее приложений, 156, Cambridge University Press, стр. 277–303, arXiv:1505.05825, МИСТЕР  3380176
• Ирани, Сэнди (1994), "Раскраска индуктивных графиков в режиме онлайн", Алгоритмика, 11 (1): 53–72, Дои:10.1007 / BF01294263, МИСТЕР  1247988.
• Janczewski, R .; Кубале, М .; Манушевский, К .; Пиваковски, К. (2001), "Наименьший трудноокрашиваемый граф для алгоритма DSATUR", Дискретная математика, 236 (1–3): 151–165, Дои:10.1016 / S0012-365X (00) 00439-8, МИСТЕР  1830607.
• Kierstead, H.A .; Троттер, В. Т. (1981), "Экстремальная задача рекурсивной комбинаторики", Труды Двенадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям, Vol. II (Батон-Руж, штат Луизиана, 1981), Congressus Numerantium, 33: 143–153, МИСТЕР  0681909. Как цитирует Иранский (1994).
• Косовски, Адриан; Манушевский, Кшиштоф (2004), «Классическая раскраска графов», в Кубале, Марек (ред.), Раскраски графиков, Современная математика, 352, Провиденс, Род-Айленд: Американское математическое общество, стр. 1–19, Дои:10.1090 / conm / 352/06369, МИСТЕР  2076987
• Кучера, Лудек (1991), «Жадная раскраска - плохой вероятностный алгоритм», Журнал алгоритмов, 12 (4): 674–684, Дои:10.1016/0196-6774(91)90040-6, МИСТЕР  1130323.
• Джонсон, Дэвид С. (1974), "Наихудшее поведение алгоритмов раскраски графов", Труды Пятой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1974), Congressus Numerantium, Икс, Виннипег, Манитоба: Utilitas Math., Стр. 513–527, МИСТЕР  0389644.
• Левек, Бенджамин; Маффре, Фредерик (октябрь 2005 г.), «Раскрашивание графиков Мейниеля в линейное время» (PDF)в Распо, Андре; Дельмас, Оливье (ред.), 7-й Международный коллоквиум по теории графов (ICGT '05), 12–16 сентября 2005 г., Йер, Франция, Электронные заметки по дискретной математике, 22, Elsevier, стр. 25–28, arXiv:cs / 0405059, Дои:10.1016 / j.endm.2005.06.005. Смотрите также Левек, Бенджамин; Маффре, Фредерик (9 января 2006 г.), Ошибка: MCColor не оптимален для графов Мейниеля, arXiv:cs / 0405059.
• Ловас, Л. (1975), «Три коротких доказательства в теории графов», Журнал комбинаторной теории, Серия B, 19 (3): 269–271, Дои:10.1016/0095-8956(75)90089-1, МИСТЕР  0396344.
• Ловас, Л.; Сакс, М.Э.; Троттер, В. Т. (1989), «Алгоритм раскраски графов в режиме онлайн с сублинейным коэффициентом производительности», Дискретная математика, 75 (1–3): 319–325, Дои:10.1016 / 0012-365X (89) 90096-4, МИСТЕР  1001404.
• Маффре, Фредерик (2003), «О раскраске совершенных графов», в Рид, Брюс А.; Продажи, Клаудия Л. (ред.), Последние достижения в области алгоритмов и комбинаторики, Книги CMS по математике, 11, Springer-Verlag, стр. 65–84, Дои:10.1007/0-387-22444-0_3, ISBN  0-387-95434-1, МИСТЕР  1952983.
• Маркосян, С. Э .; Гаспарян, Г. С .; Рид, Б.А. (1996), «β-совершенные графы», Журнал комбинаторной теории, Серия B, 67 (1): 1–11, Дои:10.1006 / jctb.1996.0030, МИСТЕР  1385380.
• Матула, Дэвид В. (1968), «Теорема о минимуме и максимуме для графов с приложением к раскраске графов», Национальное собрание SIAM 1968, SIAM Обзор, 10 (4): 481–482, Дои:10.1137/1010115.
• Матула, Дэвид В .; Бек, Л. Л. (1983), "Алгоритмы наименьшего последнего упорядочения, кластеризации и раскраски графов", Журнал ACM, 30 (3): 417–427, Дои:10.1145/2402.322385, МИСТЕР  0709826.
• Миддендорф, Маттиас; Пфайффер, Франк (1990), «О сложности распознавания идеально упорядочиваемых графов», Дискретная математика, 80 (3): 327–333, Дои:10.1016 / 0012-365X (90) 90251-C, МИСТЕР  1049253.
• Митчем, Джон (1976), "О различных алгоритмах оценки хроматического числа графа", Компьютерный журнал, 19 (2): 182–183, Дои:10.1093 / comjnl / 19.2.182, МИСТЕР  0437376.
• Ниваш, Габриэль (2006), "Функция Спраг-Гранди игры Евклид", Дискретная математика, 306 (21): 2798–2800, Дои:10.1016 / j.disc.2006.04.020, МИСТЕР  2264378.
• Перейра, Фернандо Маньо Кинтау; Палсберг, Йенс (2005), «Распределение регистров путем раскраски хордовых графов», в Yi, Kwangkeun (ed.), Языки и системы программирования: Третий азиатский симпозиум, APLAS 2005, Цукуба, Япония, 2–5 ноября 2005 г., Труды, Конспект лекций по информатике, 3780, Springer, стр. 315–329, Дои:10.1007/11575467_21
• Полетто, Массимилиано; Саркар, Вивек (сентябрь 1999 г.), «Распределение регистров линейного сканирования», Транзакции ACM по языкам и системам программирования, 21 (5): 895–913, Дои:10.1145/330249.330250.
• Rose, D .; Люкер, Джордж; Тарджан, Роберт Э. (1976), «Алгоритмические аспекты исключения вершин на графах», SIAM Журнал по вычислениям, 5 (2): 266–283, Дои:10.1137/0205021, МИСТЕР  0408312.
• Симмонс, Густав Дж. (1982), "Упорядоченное хроматическое число плоских отображений", Труды тринадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1982), Congressus Numerantium, 36: 59–67, МИСТЕР  0726050
• Сисло, Мацей М. (1989), "Последовательная раскраска по сравнению с границей Уэльса – Пауэлла", Дискретная математика, 74 (1–2): 241–243, Дои:10.1016 / 0012-365X (89) 90212-4, МИСТЕР  0989136.
• Секерес, Джордж; Уилф, Герберт С. (1968), «Неравенство для хроматического числа графа», Журнал комбинаторной теории, 4: 1–3, Дои:10.1016 / S0021-9800 (68) 80081-X.
• Вишванатан, Сундар (1992), «Рандомизированная онлайн-раскраска графов», Журнал алгоритмов, 13 (4): 657–669, Дои:10.1016 / 0196-6774 (92) 90061-Г, МИСТЕР  1187207.
• Валлийский, Д. Дж. А.; Пауэлл, М. Б. (1967), "Верхняя граница хроматического числа графа и его применение к задачам планирования времени", Компьютерный журнал, 10 (1): 85–86, Дои:10.1093 / comjnl / 10.1.85.
• Закер, Манучехр (2006), "Результаты по хроматическому числу Гранди графов", Дискретная математика, 306 (2–3): 3166–3173, Дои:10.1016 / j.disc.2005.06.044, МИСТЕР  2273147.