Интервальный граф — граф пересечениймультимножестваинтервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются.
Из этого построения можно получить общие свойства интервальных графов. Так, граф G является интервальным тогда и только тогда, когда наибольшие клики графа G могут быть упорядочены так, что для любой , где ,
выполняется также для любого [1].
Эффективные алгоритмы распознавания
Определить, является ли граф интервальным можно за время путём упорядочения наибольших клик графа G.
Интервальные графы имеющее интервальное представление, в котором любые два интервала либо не пересекаются, либо вложены, являются тривиальными совершенными графами.
Правильные интервальные графы — это интервальные графы, имеющее интервальное представление, в котором никакой интервал не является собственным подмножеством никакого другого интервала. Единичные интервальные графы — это интервальные графы, имеющее интервальное представление, в котором каждый интервал имеет единичную длину. Любой правильный интервальный граф не имеет клешней. Однако обратное неверно — граф без клешней не обязательно является правильным интервальным графом[4]. Если набор сегментов является множеством, то есть повторение сегментов не разрешено, то граф является единичным интервальным графом тогда и только тогда, когда он является правильным интервальным графом[5].
Графы пересечений дугокружности образуют графы дуг окружности — класс графов, содержащий интервальные графы. Трапецеидальные графы, пересечение трапеций, все параллельные стороны которых лежат на двух параллельных прямых, являются обобщением интервальных графов.
Путевая ширина интервального графа на единицу меньше размера максимальной клики (или, что эквивалентно, на единицу меньше его хроматического числа), a путевая ширина любого графа G равна наименьшей путевой ширине интервального графа, содержащего G в качестве подграфа[6].
Случайный интервальный граф — интеревальный граф построенный по случайному семейству отрезков, например отрезки вершины отрезков могут быть выбраны например по естественному распределению на единичном отрезке.
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber. A unified approach to approximating resource allocation and scheduling // Journal of the ACM. — 2001. — Т. 48, вып. 5. — С. 1069—1090. — doi:10.1145/502102.502107.
K. S. Booth, G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // J. Comput. System Sci. — 1976. — Т. 13, вып. 3. — С. 335—379. — doi:10.1016/S0022-0000(76)80045-1.
Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. Claw-free graphs — A survey // Discrete Mathematics. — 1997. — Т. 164, вып. 1—3. — С. 87—147. — doi:10.1016/S0012-365X(96)00045-3.
Peter C. Fishburn. Interval orders and interval graphs: A study of partially ordered sets. — New York, 1985. — (Wiley-Interscience Series in Discrete Mathematics).
D. R. Fulkerson, O. A. Gross. Incidence matrices and interval graphs // Pacific Journal of Mathematics. — 1965. — Т. 15. — С. 835—855.
Martin Charles Golumbic, Ron Shamir. Complexity and algorithms for reasoning about time: a graph-theoretic approach // J. Assoc. Comput. Mach. — 1993. — Т. 40. — С. 1108—1133..
Michel Habib, Ross McConnell, Christophe Paul, Laurent Viennot. Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing // Theor. Comput. Sci.. — 2000. — Т. 234. — С. 59—84. — doi:10.1016/S0304-3975(97)00241-7.
F.S. Roberts. Proof Techniques in Graph Theory. — Academic Press, New York, 1969. — С. 139—146.