Ausflug Graphentheorie

Chordale Graphen G mathend000# sind perfekt: für jeden induzierten Teilgraphen HG mathend000# ist die Cliquenzahl ω(H) mathend000# ist gleich der chromatischen Zahl χ(H) mathend000#.

Weiter Klassen perfekter Graphen sind:

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

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

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



2014-03-31