Chain graph

Chain graph --- цепной граф.

A bipartite graph [math]\displaystyle{ G = (P,Q,E) }[/math] is called a chain graph if there is an ordering [math]\displaystyle{ \pi }[/math] of the vertices in [math]\displaystyle{ P }[/math], [math]\displaystyle{ \pi: \; \{1, \ldots, |P|\} \rightarrow P }[/math], such that

[math]\displaystyle{ N(\pi(1)) \subseteq N(\pi(2)) \subseteq \cdots \subseteq N(\pi(|P|)). }[/math]

Here [math]\displaystyle{ N(v) }[/math] is a neighborhoodof [math]\displaystyle{ v }[/math]. It is known that [math]\displaystyle{ G }[/math] is a chain graph iff it does not contain an independent pair of edges (an induced [math]\displaystyle{ 2K_{2} }[/math]).