Ausflug Graphentheorie

Chordale Graphen G sind perfekt: für jeden induzierten Teilgraphen H $ \subseteq$ G ist die Cliquenzahl $ \omega$(H) ist gleich der chromatischen Zahl $ \chi$(H).

Weiter Klassen perfekter Graphen sind:

Strong Perfect Graph Theorem (Vermutung: Claude Berge 1960, Beweis: Maria Chudnovsky und Paul Seymor 2006):

G perfekt $ \iff$ G enthält kein C2k+1 oder $ \overline{{C_{2k+1}}}$ für k$ \ge$2.

http://users.encs.concordia.ca/~chvatal/perfect/spgt.html



2009-06-22