Permutation graph

Permutation graph --- перестановочный граф, граф перестановки

If [math]\displaystyle{ \pi }[/math] is a permutation of the numbers [math]\displaystyle{ 1, \ldots, n }[/math], we can construct an undirected graph [math]\displaystyle{ G[\pi] = (V,E) }[/math] with a vertex set [math]\displaystyle{ V = \{1, \ldots, n\} }[/math] and an edge set [math]\displaystyle{ E }[/math]:

[math]\displaystyle{ (i,j) \in E \Leftrightarrow (i - j)(\pi_{i}^{-1} - \pi_{j}^{-1}) \lt 0. }[/math]

An undirected graph is called a permutation graph if there exists a permutation [math]\displaystyle{ \pi }[/math] such that [math]\displaystyle{ G \cong G[\pi] }[/math]. It is known that the complement of a permutation graph is also a permutation graph and a permutation graph is a comparability graph.