Индифферентный граф

Индифферентный граф (Indifference graph) — Неориентированный граф $\,G$ является индифферентным графом, если существует действительная функция $\,f$ на вершинах такая, что вершины $\,u$ и $\,v$ смежные, если и только если $|f(u)-f(v)| \leq 1$. Это понятие ввел Ф.Робертс в 1969 г.; он же показал, что этот класс графов эквивалентен классу единичных интервальных графов.

Литература

• [J. Graph Theory]