Cograph

Материал из WikiGrapp
Перейти к:навигация, поиск

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.