Ausflug Graphentheorie

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

Weiter Klassen perfekter Graphen sind:

• bipartite Graphen, z. B. Bäume
• split-Graphen, Intervallgraphen
• (C₅ mathend000# ist nicht perfekt)

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 C_2k+1 mathend000# oder $\overline{{C_{2k+1}}}$ mathend000# für k≥2 mathend000#.

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