Cograph

Cograph — кограф.

1. $\,G$ is a cograph if $\,G$ is the comparability graph of a series-parallel poset. The class of cographs should not be confused with the class of series-parallel graphs.

The following recursive definition describes also the cographs:

(1) a one-vertex graph is a cograph;.

(2) if $\,G_{1} = (V_{1}, E_{1})$ and $\,G_{2} = (V_{2}, E_{2})$ are cographs, then $G = (V_{1} \cup V_{2}, E_{1} \cup E_{2})$ is also a cograph;

(3) if $\,G = (V, E)$ is a cograph, then $\bar{G} = (V, \bar{E})$ is also a cograph;

(4) there are no other cographs.

2. A cograph is a graph without $\,P_{4}$.

Литература

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