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:

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

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

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

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