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

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

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

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

Алгоритм

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

На языке Python алгоритм можно выразить так:

def  first_available ( colors ): """Возвращает наименьшее неотрицательное целое число, не входящее в заданный набор цветов.  """ color = 0 while color in colors : color += 1 return color             def  greedy_coloring ( G ,  order ): """Найти жадную раскраску G в заданном порядке.  Предполагается, что представление G похоже на https://www.python.org/doc/essays/graphs/,  позволяя перебирать соседей узла/вершины с помощью "for w in G[node]".  Возвращаемое значение — словарь, сопоставляющий вершины с их цветами.  """  coloring  =  dict ()  for  node  in  order :  used_neighbour_colors  =  { coloring [ nbr ]  for  nbr  in  G [ node ]  if  nbr  in  coloring }  coloring [ node ]  =  first_available ( used_neighbour_colors )  return  coloring

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

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

Выбор заказа

Различные порядки вершин графа могут привести к тому, что жадная раскраска будет использовать разное количество цветов, начиная от оптимального количества цветов и заканчивая, в некоторых случаях, количеством цветов, пропорциональным количеству вершин в графе. Например, граф короны (граф, образованный из двух непересекающихся наборов из $n /2$ вершин ${a 1, a 2, ...$ } и ${b 1, b 2, ...$ } путем соединения $a i$ с $b j$ всякий раз, когда $i \neq j$ ) может быть особенно плохим случаем для жадной раскраски. При порядке вершин $a 1, b 1, a 2, b 2, ...$ жадная раскраска будет использовать $n /2$ цветов, по одному цвету для каждой пары $(a i, b i)$ . Однако оптимальное количество цветов для этого графа равно двум, один цвет для вершин $a i$ и другой для вершин $b i$ . ^[5] Существуют также графы, в которых с высокой вероятностью случайно выбранный порядок вершин приводит к количеству цветов, намного большему, чем минимум. ^[6] Поэтому при жадной раскраске важно тщательно выбирать порядок вершин.

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

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

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

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

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

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

Графики, для которых порядок не имеет значения

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

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

Вырождение

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

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

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

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

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

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

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

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

Онлайн-выбор

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

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

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

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

Приложения

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

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

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

Примечания

^ Митчем (1976).
^ Аб Хоанг и Шритаран (2016), теорема 28.33, стр. 738; Хусфельдт (2015), Алгоритм G
^ ab Frieze & McDiarmid (1997).
^ ab Уэлш и Пауэлл (1967).
^ Джонсон (1974); Хасфельдт (2015).
^ Кучера (1991); Хусфельдт (2015).
^ Хусфельдт (2015).
^ Маффрей (2003).
^ Роуз, Люкер и Тарьян (1976).
^ Хватал (1984); Хусфельдт (2015).
^ Миддендорф и Пфайффер (1990).
^ abcd Закер (2006).
^ Кристен и Селков (1979).
^ Митчем (1976); Хусфельдт (2015).
^ Матула и Бек (1983).
^ Уэлш и Пауэлл (1967); Хасфельдт (2015).
^ Матула (1968); Секерес и Уильф (1968).
^ ab Косовски и Манушевски (2004).
^ Маркосян, Гаспарян и Рид (1996); Маффрей (2003).
^ Маркосян, Гаспарян и Рид (1996).
^ Греф, Штумпф и Вайсенфельс (1998).
^ Брелаз (1979); Левек и Мафре (2005).
^ Брелаз (1979).
^ Янчевски и др. (2001).
^ Левек и Маффрей (2005).
^ ab Irani (1994).
^ Ловас, Сакс и Троттер (1989); Вишванатан (1992).
^ Кирстед и Троттер (1981).
^ Симмонс (1982); Эрдеш и др. (1987).
^ Полетто и Саркар (1999). Хотя Полетто и Саркар описывают свой метод распределения регистров как не основанный на раскраске графа, он, по-видимому, аналогичен жадной раскраске.
^ Перейра и Палсберг (2005).
^ Например, см. раздел 1.1 Ниваша (2006).
^ Ловас (1975).

Ссылки

Брелаз, Даниэль (апрель 1979 г.), «Новые методы раскраски вершин графа», Сообщения ACM , 22 (4): 251–256, doi : 10.1145/359094.359101 , S2CID 14838769
Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые свойства идеальной раскраски графов», Журнал комбинаторной теории , Серия B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR 0539075
Chvátal, Václav (1984), «Совершенно упорядочиваемые графы», в Berge, Claude ; Chvátal, Václav (ред.), Topics in Perfect Graphs , Annals of Discrete Mathematics, т. 21, Амстердам: North-Holland, стр. 63–68. Как цитирует Маффрей (2003).
Erdős, P. ; Hare, WR; Hedetniemi, ST; Laskar, R. (1987), "О равенстве чисел Гранди и охроматических чисел графа" (PDF) , Журнал теории графов , 11 (2): 157–159, doi :10.1002/jgt.3190110205, MR 0889347.
Фриз, Алан ; МакДиармид, Колин (1997), «Алгоритмическая теория случайных графов», Случайные структуры и алгоритмы , 10 (1–2): 5–42, doi :10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.3.CO;2-6, MR 1611517.
Греф, А.; Штумпф, М.; Вайсенфельс, Г. (1998), «О дисковых графах единиц раскраски», Algorithmica , 20 (3): 277–293, doi : 10.1007/PL00009196, MR 1489033, S2CID 36161020.
Hoàng, Chinh T.; Sritharan, R. (2016), «Глава 28. Совершенные графы», в Thulasiraman, Krishnaiyan; Arumugam, Subramanian; Brandstädt, Andreas; Nishizeki, Takao (ред.), Handbook of Graph Theory, Combinatory Optimization, and Algorithms , Chapman & Hall/CRC Computer and Information Science Series, т. 34, CRC Press, стр. 707–750, ISBN 9781420011074.
Husfeldt, Thore (2015), «Алгоритмы раскраски графов», в Beineke, Lowell W.; Wilson, Robin J. (ред.), Topics in Chromatic Graph Theory , Encyclopedia of Mathematics and its Applications, т. 156, Cambridge University Press, стр. 277–303, arXiv : 1505.05825 , MR 3380176
Ирани, Сэнди (1994), «Раскраска индуктивных графов в режиме онлайн», Algorithmica , 11 (1): 53–72, doi :10.1007/BF01294263, MR 1247988, S2CID 181800.
Janczewski, R.; Kubale, M.; Manuszewski, K.; Piwakowski, K. (2001), "Наименьший труднораскрашиваемый граф для алгоритма DSATUR", Discrete Mathematics , 236 (1–3): 151–165, doi : 10.1016/S0012-365X(00)00439-8 , MR 1830607.
Кирстед, HA; Троттер, WT (1981), «Экстремальная задача в рекурсивной комбинаторике», Труды Двенадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям, т. II (Батон-Руж, Луизиана, 1981), Congressus Numerantium , 33 : 143–153, MR 0681909. Цитируется по Ирани (1994).
Kosowski, Adrian; Manuszewski, Krzysztof (2004), «Классическая раскраска графов», в Kubale, Marek (ред.), Graph Colorings , Contemporary Mathematics, т. 352, Providence, Rhode Island: American Mathematical Society, стр. 1–19, doi : 10.1090/conm/352/06369, ISBN 978-0-8218-3458-9, МР 2076987
Кучера, Людек (1991), «Жадная раскраска — плохой вероятностный алгоритм», Журнал алгоритмов , 12 (4): 674–684, doi :10.1016/0196-6774(91)90040-6, MR 1130323.
Джонсон, Дэвид С. (1974), «Поведение алгоритмов раскраски графов в наихудшем случае», Труды Пятой юго-восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский атлантический университет, Бока-Ратон, Флорида, 1974) , Congressus Numerantium, т. X, Виннипег, Манитоба: Utilitas Math., стр. 513–527, MR 0389644.
Lévêque, Benjamin; Maffray, Frédéric (октябрь 2005 г.), «Раскраска графов Мейниэля за линейное время» (PDF) , в Raspaud, André; Delmas, Olivier (ред.), 7-й Международный коллоквиум по теории графов (ICGT '05), 12–16 сентября 2005 г., Йер, Франция , Electronic Notes in Discrete Mathematics, т. 22, Elsevier, стр. 25–28, arXiv : cs/0405059 , doi :10.1016/j.endm.2005.06.005, S2CID 6262680. См. также Левек, Бенджамин; Маффрэ, Фредерик (9 января 2006 г.), Ошибка: MCColor неоптимален для графиков Мейниэля , arXiv : cs/0405059.
Ловас, Л. (1975), «Три коротких доказательства в теории графов», Журнал комбинаторной теории , Серия B, 19 (3): 269–271, doi : 10.1016/0095-8956(75)90089-1 , MR 0396344.
Ловас, Л.; Сакс , М.Е .; Троттер, В.Т. (1989), «Онлайн-алгоритм раскраски графов с сублинейным отношением производительности», Дискретная математика , 75 (1–3): 319–325, doi : 10.1016/0012-365X(89)90096-4 , MR 1001404.
Maffray, Frédéric (2003), «О раскраске совершенных графов», в Reed, Bruce A. ; Sales, Cláudia L. (ред.), Recent Advances in Algorithms and Combinatorics , CMS Books in Mathematics, т. 11, Springer-Verlag, стр. 65–84, doi :10.1007/0-387-22444-0_3, ISBN 0-387-95434-1, г-н 1952983.
Маркосян, С. Э.; Гаспарян, Г. С.; Рид, БА (1996), "β-совершенные графы", Журнал комбинаторной теории , Серия B, 67 (1): 1–11, doi : 10.1006/jctb.1996.0030 , MR 1385380.
Матула, Дэвид В. (1968), «Теорема о минимуме-максимуме для графов с применением к раскраске графов», Национальное собрание SIAM 1968 г., Обзор SIAM , 10 (4): 481–482, doi :10.1137/1010115.
Матула, Дэвид В.; Бек, Л.Л. (1983), «Алгоритмы упорядочения наименьшего последнего элемента, кластеризации и раскраски графов», Журнал ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR 0709826.
Миддендорф, Маттиас; Пфайффер, Франк (1990), «О сложности распознавания совершенно упорядочиваемых графов», Дискретная математика , 80 (3): 327–333, doi : 10.1016/0012-365X(90)90251-C , MR 1049253.
Митчем, Джон (1976), «О различных алгоритмах оценки хроматического числа графа», The Computer Journal , 19 (2): 182–183, doi : 10.1093/comjnl/19.2.182 , MR 0437376.
Ниваш, Габриэль (2006), «Функция Шпрага–Гранди игры Евклид», Дискретная математика , 306 (21): 2798–2800, doi : 10.1016/j.disc.2006.04.020 , MR 2264378.
Перейра, Фернанду Маньо Кинтао; Палсберг, Йенс (2005), «Распределение регистров посредством раскраски хордальных графов», в книге Йи, Квангын (ред.), Языки программирования и системы: Третий азиатский симпозиум, APLAS 2005, Цукуба, Япония, 2–5 ноября 2005 г., Труды , Конспекты лекций по информатике, вып. 3780, Springer, стр. 315–329, номер документа : 10.1007/11575467_21, ISBN. 978-3-540-29735-2
Полетто, Массимилиано; Саркар, Вивек (сентябрь 1999 г.), «Распределение регистров линейного сканирования», ACM Transactions on Programming Languages and Systems , 21 (5): 895–913, doi : 10.1145/330249.330250 , S2CID 18180752.
Роуз, Д.; Люкер, Джордж; Тарьян, Роберт Э. (1976), «Алгоритмические аспекты исключения вершин на графах», SIAM Journal on Computing , 5 (2): 266–283, doi :10.1137/0205021, MR 0408312.
Симмонс, Густавус Дж. (1982), «Упорядоченное хроматическое число плоских карт», Труды тринадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1982), Congressus Numerantium , 36 : 59–67, MR 0726050
Sysło, Maciej M. (1989), «Последовательная раскраска против границы Уэлша–Пауэлла», Discrete Mathematics , 74 (1–2): 241–243, doi : 10.1016/0012-365X(89)90212-4 , MR 0989136.
Секереш, Джордж ; Вильф, Герберт С. (1968), «Неравенство для хроматического числа графа», Журнал комбинаторной теории , 4 : 1–3, doi : 10.1016/S0021-9800(68)80081-X.
Вишванатан, Сундар (1992), «Случайная раскраска графов в режиме онлайн», Журнал алгоритмов , 13 (4): 657–669, doi :10.1016/0196-6774(92)90061-G, MR 1187207.
Уэлш, DJA ; Пауэлл, MB (1967), «Верхняя граница хроматического числа графа и ее применение к задачам составления расписания», The Computer Journal , 10 (1): 85–86, doi : 10.1093/comjnl/10.1.85.
Закер, Манучехр (2006), «Результаты по хроматическому числу Гранди для графов», Дискретная математика , 306 (2–3): 3166–3173, doi : 10.1016/j.disc.2005.06.044 , MR 2273147.