
\begin{slide}{Ausflug Graphentheorie}

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

Weiter Klassen perfekter Graphen sind:
\begin{itemize}\itemsep0pt
\item bipartite Graphen, z. B. Bäume
\item split-Graphen, Intervallgraphen
\item ($C_5$ ist nicht perfekt)
\end{itemize}

\emph{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$.

\url{http://users.encs.concordia.ca/~chvatal/perfect/spgt.html}

\end{slide}

