Интервальный граф

Интервальный граф (Interval graph) - граф пересечений множества замкнутых интервалов на вещественной прямой. Комбинаторную характеризацию интервальных графов дает следующая теорема.

Справедлива теорема (Gilmore and Hofman, 1964) об эквивалентности следующих свойств неориентированного графа [math]\displaystyle{ G }[/math]:

1. [math]\displaystyle{ G }[/math] --- интервальный граф.

2. Максимальные клики в [math]\displaystyle{ G }[/math] могут быть линейно упорядочены так, что для каждой вершины [math]\displaystyle{ x }[/math] в [math]\displaystyle{ G }[/math] максимальные клики, содержащие [math]\displaystyle{ x }[/math], встречаются последовательно.

3. [math]\displaystyle{ G }[/math] не содержит безхордового 4-цикла и его дополнение [math]\displaystyle{ \bar{{G} }[/math] есть граф сравнимости.

И.г. называется собственным интервальным графом (proper interval graph), если ни один интервал в интервальном представлении не содержит полностью другой, и единичным (unit interval graph), если все интервалы единичной длины.

Литература

[Миркин-Родин],

[Евстигнеев/98],

[J. Graph Theory]