Cograph

Cograph — кограф.

1. [math]\displaystyle{ \,G }[/math] is a cograph if [math]\displaystyle{ \,G }[/math] 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 [math]\displaystyle{ \,G_{1} = (V_{1}, E_{1}) }[/math] and [math]\displaystyle{ \,G_{2} = (V_{2}, E_{2}) }[/math] are cographs, then [math]\displaystyle{ G = (V_{1} \cup V_{2}, E_{1} \cup E_{2}) }[/math] is also a cograph;

(3) if [math]\displaystyle{ \,G = (V, E) }[/math] is a cograph, then [math]\displaystyle{ \bar{G} = (V, \bar{E}) }[/math] is also a cograph;

(4) there are no other cographs.

2. A cograph is a graph without [math]\displaystyle{ \,P_{4} }[/math].

Литература

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