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

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

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

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

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

Алгоритм [ править ]

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

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

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

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

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

Выбор заказа [ править ]

Различный порядок вершин графа может привести к тому, что жадная раскраска будет использовать разное количество цветов, от оптимального количества цветов до, в некоторых случаях, количества цветов, пропорционального количеству вершин в графе. Например, граф короны (граф, образованный двумя непересекающимися наборами из n / 2 вершин { a 1 , a 2 , ... } и { b 1 , b 2 , ... } путем соединения a i с b j всякий раз, когда я ≠ 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] Так же сложно, как найти хороший порядок вершин для жадной раскраски, так же как и найти плохой порядок вершин. NP-полно определить для данного графа G и числа k , существует ли такой порядок вершин графа G, который заставляет жадный алгоритм использовать k или более цветов. В частности, это означает, что для G трудно найти наихудший порядок . [12]

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

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

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

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

Вырождение [ править ]

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

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

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

Адаптивные заказы [ править ]

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

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

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

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

Онлайн-выбор [ править ]

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

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

Экономная окраска [ править ]

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

Приложения [ править ]

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

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

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

Примечания [ править ]

  1. ^ Митч (1976) .
  2. ^ a b Hoàng & Sritharan (2016) , теорема 28.33, стр. 738 ; Хусфельдт (2015) , алгоритм G
  3. ^ a b Frieze & McDiarmid (1997) .
  4. ^ a b Welsh & Powell (1967) .
  5. ^ Джонсон (1974) ; Хусфельдт (2015) .
  6. ^ Кучера (1991) ; Хусфельдт (2015) .
  7. ^ Husfeldt (2015) .
  8. ^ Maffray (2003) .
  9. ^ Rose, Lueker & Тарьян (1976) .
  10. ^ Chvátal (1984) ; Husfeldt (2015) .
  11. Перейти ↑ Middendorf & Pfeiffer (1990) .
  12. ^ а б в г Закер (2006) .
  13. ^ Крестят & Selkow (1979) .
  14. ^ Митчем (1976) ; Хусфельдт (2015) .
  15. ^ Матула и Бек (1983) .
  16. ↑ Валлийский и Пауэлл (1967) ; Хусфельдт (2015) .
  17. ^ Матула (1968) ; Секерес и Вильф (1968) .
  18. ^ a b Kosowski & Manuszewski (2004) .
  19. ^ Маркосян, Гаспарян и Рид (1996) ; Маффрей (2003) .
  20. ^ Маркосян, Гаспарян и Рид (1996) .
  21. ^ Gräf, Штумпф и Weißenfels (1998) .
  22. ^ Brélaz (1979) ; Левек и Маффре (2005) .
  23. ^ Brélaz (1979) .
  24. ^ Janczewski et al. (2001) .
  25. ^ Lévêque & Maffray (2005) .
  26. ^ а б Ирани (1994) .
  27. ^ Lovász, Saks & Trotter (1989) ; Вишванатан (1992) .
  28. ^ Кирстед & Trotter (1981) .
  29. ^ Симмонс (1982) ; Erds et al. (1987) .
  30. ^ Poletto & Саркар (1999) . Хотя Полетто и Саркар описывают свой метод распределения регистров как не основанный на раскраске графов, он похож на жадную раскраску.
  31. ^ Pereira & Palsberg (2005) .
  32. ^ Например, смотрите Раздел 1.1 Nivasch (2006) .
  33. ^ Lovász (1975) .

Ссылки [ править ]

  • Brélaz, Daniel (апрель 1979), "Новые методы цвета вершин графа", Communications по АКМ , 22 (4): 251-256, DOI : 10,1145 / 359094,359101
  • Кристен, Клод А .; Сельков, Стэнли М. (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 (eds.), Topics in Perfect Graphs , Annals of Discrete Mathematics, 21 , Amsterdam: North-Holland, стр. 63–68.. Цитируется Maffray (2003) .
  • Erdős, P .; Заяц, WR; Хедетниеми, СТ; Laskar, Р. (1987), "О равенстве Grundy и ochromatic чисел графа" (PDF) , Журнал теории графов , 11 (2): 157-159, DOI : 10.1002 / jgt.3190110205 , МР  0889347.
  • Frieze, Алан ; МакДирмид, Colin (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.
  • Gräf, A .; Штумпф, М .; Вайсенфельс, G. (1998), "О окраски единичного круга графов", Algorithmica , 20 (3): 277-293, DOI : 10.1007 / PL00009196 , МР  1489033.
  • Hoàng, Chinh T .; Шритаран, Р. (2016), «Глава 28. Совершенные графы», в Туласирамане, Кришнайян; Арумугам, субраманианский; Брандштадт, Андреас; Нишизеки, Такао (ред.), Справочник по теории графов, комбинаторной оптимизации и алгоритмов , Chapman & Hall / CRC Computer and Information Science Series, 34 , CRC Press, pp. 707–750, ISBN 9781420011074.
  • Husfeldt, Thore (2015), «Алгоритмы раскраски графов», в Beineke, Lowell W .; Уилсон, Робин Дж. (Ред.), Topics in Chromatic Graph Theory , Encyclopedia of Mathematics and its Applications, 156 , Cambridge University Press, pp. 277–303, arXiv : 1505.05825 , MR  3380176
  • Ираньте, Сэнди (1994), "Окрашивание индуктивных график он-лайн", Algorithmica , 11 (1): 53-72, DOI : 10.1007 / BF01294263 , МР  1247988.
  • Janczewski, R .; Кубале, М .; Манушевский, К .; Piwakowski, К. (2001), "Самый маленький граф труднодоступные цвета для алгоритма DSATUR", дискретной математики , 236 (1-3): 151-165, DOI : 10.1016 / S0012-365X (00) 00439-8 , Руководство по ремонту  1830607.
  • Кирстед, штат Джорджия; Троттер, В. Т. (1981), "Экстремальная задача в рекурсивной комбинаторике", Труды Двенадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям, Vol. II (Батон-Руж, штат Луизиана, 1981), Congressus Numerantium , 33 : 143–153, MR  0681909. Как указано на Irani (1994) .
  • Косовски, Адриан; Манушевский, Кшиштоф (2004), «Классическая раскраска графов», в Кубале, Марек (ред.), Раскраски графов , Современная математика, 352 , Провиденс, Род-Айленд: Американское математическое общество, стр. 1–19, doi : 10.1090 / conm / 352/06369 , MR  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.
  • Левек, Бенджамин; Маффре, Фредерик (октябрь 2005 г.), «Раскрашивание графов Мейниеля за линейное время» (PDF) , в Распо, Андре; Дельмас, Оливье (ред.), 7-й Международный коллоквиум по теории графов (ICGT '05), 12–16 сентября 2005 г., Йер, Франция , Электронные заметки по дискретной математике, 22 , Elsevier, стр. 25–28, arXiv : cs / 0405059 , DOI : 10.1016 / j.endm.2005.06.005. См. Также Левек, Бенджамин; Маффре, Фредерик (9 января 2006 г.), Ошибка: MCColor не оптимален для графов Мейниеля , arXiv : cs / 0405059.
  • Ловаса, Л. (1975), "Три короткое доказательство в теории графов", Журнал комбинаторной теории , Series B, 19 (3): 269-271, DOI : 10,1016 / 0095-8956 (75) 90089-1 , МР  0396344.
  • Lovász, L .; Saks, ME ; Trotter, WT (1989), "Он-лайн раскраски граф алгоритма с сублинейным соотношением производительности", дискретная математика , 75 (1-3): 319-325, DOI : 10.1016 / 0012-365X (89) 90096-4 , М.Р.  1001404.
  • Маффре, Фредерик (2003), «О раскраске совершенных графов», в Риде, Брюс А .; Продажи, Клаудия Л. (ред.), Недавние достижения в области алгоритмов и комбинаторики , Книги CMS по математике, 11 , Springer-Verlag, стр. 65–84, DOI : 10.1007 / 0-387-22444-0_3 , ISBN 0-387-95434-1, MR  1952983.
  • Маркосян С.Е .; Гаспарян, Г.С. Рид, Б. А. (1996), "бета-совершенных графов", Журнал комбинаторной теории , серии B, 67 (1): 1-11, DOI : 10,1006 / jctb.1996.0030 , MR  1385380.
  • Matula, David W. (1968), "Теорема минимакса для графов с приложением к раскраске графа", SIAM 1968 Национального совещание, SIAM Review , 10 (4): 481-482, DOI : 10,1137 / 1010115.
  • Матула, Дэвид В .; Бек, LL (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-С , МР  1049253.
  • Митч, Джон (1976), "О различных алгоритмах для оценки хроматического числа графа", Компьютерный журнал , 19 (2): 182-183, DOI : 10,1093 / comjnl / 19.2.182 , МР  0437376.
  • Nivasch, Габриэль (2006), "О Спраге-Гранди функции игры Евклид", дискретная математика , 306 (21): 2798-2800, DOI : 10.1016 / j.disc.2006.04.020 , МР  2264378.
  • Перейра, Фернандо Маньо Кинтау; Палсберг, Йенс (2005), «Распределение регистров с помощью раскраски хордовых графов», в Yi, Kwangkeun (ed.), Programming Languages ​​and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, 2–5 ноября 2005 г., Proceedings , Lecture Notes в области компьютерных наук, 3780 ., Springer, С. 315-329, DOI : 10.1007 / 11575467_21
  • Полетто, Массимилиано; Саркар, Вивек (сентябрь 1999), "Линейное сканирование распределение регистров", ACM Сделки по Языки программирования и системы , 21 (5): 895-913, DOI : 10,1145 / 330249.330250.
  • Rose, D .; Люкер, Джордж; Тарьян, Роберт Е. (1976), "Алгоритмические аспекты устранения вершины на графах", SIAM журнал по вычислениям , 5 (2): 266-283, DOI : 10,1137 / 0205021 , МР  0408312.
  • Симмонс, Густав Дж. (1982), «Упорядоченное хроматическое число плоских отображений», Труды тринадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1982), Congressus Numerantium , 36 : 59–67 , Руководство по ремонту  0726050
  • Сисло, Мацей М. (1989), «Последовательная раскраска по сравнению с границей Уэлша – Пауэлла», Дискретная математика , 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 , МР  1187207.
  • Валлийский, DJA ; Пауэлл, МБ (1967), "Верхняя граница хроматического числа графа и его применение к задачам расписания", Компьютерный журнал , 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.