Cocomparability ordering

Cocomparability ordering — косравнимое упорядочение.

A graph $\,G$ has a cocomparability ordering if there exists a linear order $\,<$ on the set of its vertices such that for every choice of vertices $\,u, v, w$ the following property holds

$u < v < w \wedge (u,w) \in E \Rightarrow (u,v) \in E \vee (v,w) \in E.$

A graph is a cocomparability graph if it admits a cocomparability ordering.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.