Интервальное хроматическое число

Интервальное хроматическое число X_<(H) упорядоченного графа H — это минимальное число интервалов, на которое может быть разбит (линейно упорядоченный) набор вершин H так, что никакие две вершины, принадлежащие одному и тому же интервалу, не смежны в H.

Отличие от хроматического числа

Интервальное хроматическое число интересно тем, что оно просто вычисляется. Более того, с помощью простого жадного алгоритма можно эффективно найти оптимальное разбиение набора вершин H на X_<(H) независимых интервалов. Это сильно контрастирует с фактом, что для обычного хроматического числа графа даже его аппроксимация является NP-трудной задачей.

Пусть K(H) — хроматическое число упорядоченного графа H. Тогда для любого упорядоченного графа H выполняется неравенство $X_{<}(H)\geqslant K(H)$.

Следует заметить, что у конкретного графа H и изоморфных ему графов хроматическое число одно и то же, а вот интервальное хроматическое число может отличаться. Оно зависит от упорядочения вершин графа.

Литература

• János Pach, Gabor Tardos. Forbidden Pattern and Unit Distances // 21-st Annual Symposium ACM. — ACM, 2005.