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

Этот граф может быть раскрашен 3 цветами 12 способами.

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

Терминология, в которой метки называются цветами, происходит от раскраски политических карт. Такие метки как красный или синий используются, только когда число цветов мало, обычно же подразумевается, что метки являются целыми числами ${\displaystyle \{1,2,3,...\}}$.

Раскраска с использованием ${\displaystyle k}$ цветов называется ${\displaystyle k}$-раскраской. Наименьшее число цветов, необходимое для раскраски графа ${\displaystyle G}$, называется его хроматическим числом и часто записывается как ${\displaystyle \chi (G)}$. Иногда используется ${\displaystyle \gamma (G)}$, с тех пор как ${\displaystyle \chi (G)}$ обозначает Эйлерову характеристику. Подмножество вершин, выделенных одним цветом, называется цветовым классом, каждый такой класс формирует независимый набор. Таким образом, ${\displaystyle k}$-раскраска — это то же самое, что и разделение вершин на ${\displaystyle k}$ независимых наборов[1].

Пусть ${\displaystyle G}$ — произвольный граф с множеством вершин ${\displaystyle V}$. Фиксируем два положительных вещественных числа ${\displaystyle a<b\leq 2a}$, и будем рассматривать ${\displaystyle V}$ как метрическое пространство, в котором расстояния между смежными вершинами равны ${\displaystyle b}$, в все остальные ненулевые расстояния равны ${\displaystyle a}$. Обозначим через ${\displaystyle a\Delta _{m}}$ метрическое пространство, состоящее из ${\displaystyle m}$ точек, удаленных друг от друга на расстояние ${\displaystyle a}$. Наконец, для любых двух метрических пространств ${\displaystyle X}$ и ${\displaystyle Y}$, через ${\displaystyle d_{GH}(X,Y)}$ обозначим расстояние Громова-Хаусдорфа между ${\displaystyle X}$ и ${\displaystyle Y}$. Тогда имеет место следующий результат.

Теорема (А.О.Иванов, А.А.Тужилин)[9]: Пусть ${\displaystyle m}$ — наибольшее натуральное число, для которого ${\displaystyle d_{GH}(V,a\Delta _{m})=b}$ (если таких натуральных чисел не существует, то положим ${\displaystyle m=0}$). Тогда ${\displaystyle \chi (G)=m+1}$.

Замечание.

• Хроматическое число ${\displaystyle \chi (G)}$ равно ${\displaystyle 1}$, если и только если граф ${\displaystyle G}$ не содержит ни одного ребра. В этом случае равенство ${\displaystyle d_{GH}(V,a\Delta _{m})=b}$ не выполняется ни для какого ${\displaystyle m}$, поэтому, в силу сделанного соглашения, ${\displaystyle m=0}$, что приводит к верному равенству ${\displaystyle \chi (G)=0+1=1}$.

• По определению, ${\displaystyle \chi (G)}$ не превосходит количества ${\displaystyle n}$ элементов множества ${\displaystyle V}$. С другой стороны, несложно показать, что ${\displaystyle d_{GH}(V,a\Delta _{p})\leq \max\{a,\,b-a\}<b}$ при каждом ${\displaystyle p\geq n}$, поэтому ${\displaystyle m<n}$ и, значит, ${\displaystyle \chi (G)=m+1\leq n}$.

Хроматический многочлен — это функция ${\displaystyle P(G,t)}$, которая считает число t-раскрасок графа ${\displaystyle G}$. Из названия следует, что для заданных ${\displaystyle G}$ эта функция является многочленом, зависящим от t.

Этот факт был обнаружен Биркгофом и Льюисом при попытке доказать гипотезу четырёх красок[10].

Все не изоморфные графы из 3 вершин и их хроматические многочлены. Пустой граф E₃ (красный) допускает раскраску одним цветом, остальные — нет. Зелёный граф может быть раскрашен 3 цветами 12 способами.

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

Для графа в примере ${\displaystyle P(G,t)=t(t-1)^{2}(t-2)}$ и, конечно, ${\displaystyle P(G,4)=72}$.

Хроматический многочлен содержит по меньшей мере столько же информации о раскрашиваемости ${\displaystyle G}$, сколько и хроматическое число. В самом деле, ${\displaystyle \chi }$ — наименьшее целое положительное число, не являющееся корнем хроматического многочлена.

${\displaystyle \chi (G)=\min\{t\,\colon \,P(G,t)>0\}.}$

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

Треугольный ${\displaystyle K_{3}}$	${\displaystyle t(t-1)(t-2)}$
Полный граф ${\displaystyle K_{n}}$	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
Дерево с ${\displaystyle n}$ ребрами	${\displaystyle t(t-1)^{n}}$
Цикл ${\displaystyle C_{n}}$	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Граф Петерсена	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Рёберная раскраска графа подразумевает под собой назначение цветов ребрам так, что никакие два ребра одного цвета не принадлежат одной вершине. Эта задача эквивалентна разделению множества граней на множества независимых граней. Наименьшее число цветов, необходимое для рёберной раскраски графа ${\displaystyle G}$ — это его хроматический индекс, или рёберное хроматическое число, ${\displaystyle \chi '(G)}$.

Тотальная раскраска — это один из видов раскраски вершин и рёбер графа. Под ней подразумевают такое присвоение цветов, что ни соседние вершины, ни смежные ребра, ни вершины и ребра, которые их соединяют, не имеют одинакового цвета. Полное хроматическое число ${\displaystyle \chi ''(G)}$ графа ${\displaystyle G}$ — это наименьшее число цветов, необходимое для любой полной раскраски.

• Если ${\displaystyle G}$ — пустой граф[11],

${\displaystyle P(G,t)=1}$

• Если граф ${\displaystyle G}$ — объединение непересекающихся подграфов ${\displaystyle H}$ и ${\displaystyle K}$[11],

${\displaystyle P(G,t)=P(H,t)P(K,t)}$

• Если в ${\displaystyle G}$ есть петля[11],

${\displaystyle P(G,t)=0}$

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

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

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

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

• Если ${\displaystyle G}$ является объединением непересекающихся подграфов ${\displaystyle H}$ и ${\displaystyle K}$, то

${\displaystyle \chi (G)=max\{\chi (H),\chi (K)\}}$

• Если ${\displaystyle G}$ содержит клики размера k, тогда необходимо минимум k цветов для раскраски этой клики, другими словами хроматическое число больше, либо равно кликовому числу:

${\displaystyle \chi (G)\geq \omega (G).}$

Для интервальных графов это ограничение точно.

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

Граф ${\displaystyle G}$ является двудольным в том и только в том случае, если он не содержит циклов нечетной длины[11].

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

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

• Полные графы имеют ${\displaystyle \chi (G)=n}$ и ${\displaystyle \Delta (G)=n-1}$, графы-циклы имеют ${\displaystyle \chi (G)=3}$ и ${\displaystyle \Delta (G)=2}$, так что для них это ограничение является наилучшим, во всех других случаях, ограничение может быть улучшено: теорема Брукса[13] утверждает, что

${\displaystyle \chi (G)\leq \Delta (G)}$ для связанного, простого графа ${\displaystyle G}$, если ${\displaystyle G}$ не является ни полным графом, ни графов-циклом.

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

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

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

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

• Рёберная раскраска ${\displaystyle G}$ — это раскраска вершин его линейного графа ${\displaystyle L(G)}$. То есть

${\displaystyle \chi '(G)=\chi (L(G)).}$

• Более того[14],

Теорема Кёнига: ${\displaystyle \chi '(G)=\Delta (G)}$, если ${\displaystyle G}$ — двудольный.

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

Теорема Визинга: Граф с максимальной степенью вершины ${\displaystyle \Delta }$ имеет рёберное хроматическое число ${\displaystyle \Delta }$ или ${\displaystyle \Delta +1}$.

• Граф является k-хроматическим тогда и только тогда, когда он имеет ациклическую ориентацию, для которой длина наибольшего пути равна k. Это было доказано в теореме Галлаи — Хассе — Роя — Витавера[15].
• Для плоских графов, раскраска вершин эквивалентна нигде не нулевому потоку.
• О бесконечных графах известно намного меньше. Ниже приведены два результата для раскраски бесконечных графов.

1. Если все конечные подграфы бесконечного графа ${\displaystyle G}$ k-хроматические, то и ${\displaystyle G}$ тоже является k-хроматическим (доказывается при предположении аксиомы выбора). Это — формулировка теоремы де Брёйна — Эрдёша[16].
2. Если граф допускает полную n-раскраску для любого ${\displaystyle n\geqslant n_{0}}$, то он допускает бесконечную полную раскраску[17].

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

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

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

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

Используя динамическое программирование и оценку размера наибольшего независимого множества, в графе возможность k-раскраски может быть разрешена за время ${\displaystyle O(2,445^{n})}$[18]. Известны более быстрые алгоритмы для 3- и 4-раскрасок, работающие за время ${\displaystyle O(1,3289^{n})}$[19] и ${\displaystyle O(1,7272^{n})}$[20] соответственно.

Стягивание вершин — это операция, которая из графа ${\displaystyle G}$ делает граф ${\displaystyle G/uv}$, отождествляя вершины ${\displaystyle u}$ и ${\displaystyle v}$, удаляя соединяющие их рёбра и заменяя на одну вершину ${\displaystyle w}$, куда перенаправляются ребра, инцидентные вершинам ${\displaystyle u}$ и ${\displaystyle v}$. Эта операция играет важную роль в анализе раскраски графов.

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

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

где ${\displaystyle u}$ и ${\displaystyle v}$ — несмежные вершины, ${\displaystyle G+uv}$ — граф с добавленным ребром ${\displaystyle uv}$. Некоторые алгоритмы основаны на данном соотношении, выдавая как результат дерево, иногда называемое деревом Зыкова. Время выполнения зависит от метода выбора вершин ${\displaystyle u}$ и ${\displaystyle v}$.

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

${\displaystyle P(G-uv,t)=P(G/uv,t)+P(G,t)}$,

где ${\displaystyle u}$ и ${\displaystyle v}$ — смежные вершины, ${\displaystyle G-uv}$ — граф с удалением ребра ${\displaystyle uv}$. ${\displaystyle P(G-uv,t)}$ представляет собой число возможных правильных раскрасок графа, когда вершины ${\displaystyle u}$ и ${\displaystyle v}$ могут иметь одинаковые или различные цвета. Если ${\displaystyle u}$ и ${\displaystyle v}$ имеют разные цвета, тогда мы можем рассмотреть граф, где ${\displaystyle u}$ и ${\displaystyle v}$ смежные. Если ${\displaystyle u}$ и ${\displaystyle v}$ имеют одинаковые цвета, мы можем рассмотреть граф, где ${\displaystyle u}$ и ${\displaystyle v}$ объединены.

Выражения, данные выше, приводят к рекурсивной процедуре, названной алгоритм удаления и стягивания, сформировавшей основу для многих алгоритмов раскраски графов. Время работы удовлетворяет такому же рекуррентному соотношению, как и числа Фибоначчи, поэтому в наихудшем случае алгоритм будет работать за время ${\displaystyle ((1+{\sqrt {5}})/2)^{n+m}=O(1,6180^{n+m})}$ для n вершин и m рёбер[21]. На практике метод ветвей и границ и отбрасывание изоморфных графов позволяет избежать некоторых рекурсивных вызовов, время работы зависит от метода подбора пары вершин.

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

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

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

Если вершины упорядочены в соответствии с их степенями, алгоритм жадной раскраски использует не более чем ${\displaystyle max_{i}min\{d(v_{i})+1,i\}}$ цветов, что максимум на 1 больше, чем ${\displaystyle \Delta }$ (здесь ${\displaystyle d(v_{i})}$ — степень вершины ${\displaystyle v_{i}}$). Этот эвристический алгоритм иногда называют алгоритмом Уэлша-Пауэлла[22]. Другой алгоритм устанавливает порядок динамично, выбирая следующую вершину той, которая имеет наибольшее число смежных вершин разных цветов. Многие другие алгоритмы раскраски графов основаны на жадной раскраске и используют статические или динамические стратегии выбора порядка вершин.

В области распределённых алгоритмов встречается аналогичная задача. Допустим, вершины графа — это компьютеры, которые могут общаться между собой, если они соединены ребром. Задача состоит в том, чтобы каждый компьютер выбрал для себя «цвет», так, чтобы соседние компьютеры выбрали разные цвета. Эта задача тесно связана с проблемой нарушения симметрии. Наиболее развитые вероятностные алгоритмы работают быстрее, чем детерминированные алгоритмы для графов с достаточно большой максимальной степени вершин ${\displaystyle \Delta }$. Наиболее быстрые вероятностные алгоритмы используют технику множественных попыток[23].

В симметричных графах детерминированные распределённые алгоритмы не могут найти оптимальную раскраску вершин. Нужна дополнительная информация, чтобы избежать симметрии. Делается стандартное предположение, что первоначально каждая вершина имеет уникальный идентификатор, например, из множества ${\displaystyle \{1,2,...,N\}}$. Иными словами, предполагается, что нам дана n-раскраска. Задача состоит в том, чтобы уменьшить количество цветов от n до, например, ${\displaystyle (\Delta +1)}$. Чем больше цветов используются (например, ${\displaystyle O(\Delta )}$ вместо ${\displaystyle (\Delta +1)}$), тем меньше обменов сообщений потребуется[23].

Простая версия распределённого жадного алгоритма для ${\displaystyle (\Delta +1)}$ -раскраски требует ${\displaystyle \Theta (n)}$ раундов связи в худшем случае — информации, возможно, придется проходить с одного конца стороны сети до другого.

Наиболее простым интересным случаем является n-цикл. Ричард Коул и Узи Вишкин[24] показали, что существует распределённый алгоритм, который уменьшает количество цветов от n до ${\displaystyle O(log(n))}$, используя лишь один раз обмен сообщениями между соседями. Повторяя ту же процедуру, можно получить 3-раскраску n-цикла за ${\displaystyle O(log^{*}(n))}$ раундов связи (при условии, что даны уникальные идентификаторы узлов).

Функция ${\displaystyle log^{*}}$, итерированный логарифм, является чрезвычайно медленно растущей функцией, «почти константа». Следовательно, результаты Коула и Вишкина поднимают вопрос о том, есть ли распределённый алгоритм 3-раскраски n-цикла, который выполняется за константное время. Натан Линиал показал, что это невозможно: любой детерминированный распределённый алгоритм требует ${\displaystyle \Omega (log^{*}(n))}$ раундов связи для уменьшения N-раскраски до 3-раскраски в n-цикле[25].

Техника Коула и Вишкина также может быть применена для произвольного графа с ограниченной степенью вершин, в этом случае время работы составляет ${\displaystyle P(\Delta )+O(log^{*}(n))}$[26]. Этот метод был обобщен для графа единичных кругов Шнайдером и др[27].

Проблема раскраски рёбер также изучалась в распределённой модели. Пансонецци и Рицци достигли ${\displaystyle (2\Delta -1)}$-раскраски за ${\displaystyle O(\Delta +log^{*}(n))}$ в этой модели[28]. Нижняя граница для распределённой раскраски вершин, достигнутая Линиалом, также применима для задачи распределённой раскраски рёбер[25].

Децентрализованными называются алгоритмы, в которых не разрешена внутренняя передача сообщений (в отличие от распределённых алгоритмов, где процессы обмениваются между собой данными). Существуют эффективные децентрализованные алгоритмы, успешно справляющиеся с задачей раскраски графов. Эти алгоритмы работают в предположении, что вершина способна «чувствовать», что какая-либо из её соседних вершин раскрашена в тот же цвет, что и она. Другими словами, есть возможность определить локальный конфликт. Такое условие довольно часто выполняется в реальных прикладных задачах — например, при передаче данных по беспроводному каналу передающая станция, как правило, имеет возможность детектировать, что другая станция пытается передавать одновременно в тот же канал. Способности к получению подобной информации достаточно для того, чтобы алгоритмы, основанные на обучающихся автоматах, с вероятностью единица правильно решат задачу раскраски графа[29][30].

Раскраска графа является вычислительно сложной задачей. Узнать, допускает ли граф k-раскраску для заданного k — это NP-полная задача, кроме случаев k = 1 и k = 2. В частности, задача вычисления хроматического числа NP-сложна[31]. Задача о 3-раскраске NP-полная даже для случая планарного графа степени 4[32].

Также NP-сложной задачей является раскраска 3-раскрашиваемого графа 4 цветами[33] и k-раскрашиваемого графа ${\displaystyle k^{log(k)/25}}$ при достаточно больших значениях k[34].

Вычисление коэффициентов хроматического полинома #P-сложная задача. Доказано, что не существует ни одного FPRAS-алгоритма для вычисления хроматического полинома ни для какого рационального числа k ≥ 1,5, кроме k = 2, если только не выполнится, что NP = RP[35].

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

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

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

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

Технология цифровых водяных знаков (англ. digital watermarking) позволяет вместе с данными (будь то медиафайлы, исполняемые файлы и прочие) передать некое скрытое сообщение («водяной знак», Watermark). Такое скрытое сообщение может быть применено в защите авторских прав для идентификации владельца данных.

Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные, например — программное обеспечение систем на кристалле (system-on-chip).

Сообщение можно закодировать в том числе и в способе распределения регистров. Одну из таких техник предложили Qu и Potkonjak[37] (поэтому её иногда называют QP-алгоритмом).

Состоит она вот в чём: пусть ${\displaystyle G}$ — граф несовместимости (интерференционный граф) распределения регистров процессора, о котором говорилось выше. Его раскраска используется в программе — причём, используется так, что допустимо поменять содержимое графа с небольшим увеличением его хроматического числа. Оказывается возможно закодировать послание в программном продукте с помощью раскраски графа ${\displaystyle G}$, то есть распределения регистров.

Извлечь это сообщение можно путём сравнением распределения регистров с исходной раскраской;[38] существуют и способы удостовериться в том, было ли некое сообщение закодировано в программе без использования исходного.

В дальнейшем разные авторы развивали и уточняли идеи Qu и Potkonjak[39].[38][40]

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

Решение головоломки судоку можно рассматривать как завершение раскраски 9 цветами заданного графа из 81 вершины.