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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

  • [J. Graph Theory]