Интервальное хроматическое число
Интервальное хроматическое число X<(H) Шаблон:Не переведено 5 H — это минимальное число интервалов, на которое может быть разбит (линейно упорядоченный) набор вершин H так, что никакие две вершины, принадлежащие одному и тому же интервалу, не смежны в HШаблон:Sfn.
Отличие от хроматического числа
Интервальное хроматическое число интересно тем, что оно просто вычисляется. Более того, с помощью простого жадного алгоритма можно эффективно найти оптимальное разбиение набора вершин H на X<(H) независимых интервалов. Это сильно контрастирует с фактом, что для обычного хроматического числа графа даже его аппроксимация является NP-трудной задачей.
Пусть K(H) — хроматическое число упорядоченного графа H. Тогда для любого упорядоченного графа H выполняется неравенство .
Следует заметить, что у конкретного графа H и изоморфных ему графов хроматическое число одно и то же, а вот интервальное хроматическое число может отличаться. Оно зависит от упорядочения вершин графа.