Perfektion

Satz: G chordal $\Rightarrow$ $\chi$(G) = $\omega$(G).

Def: G heißt perfekt, falls für alle induzierten Teilgraphen H $\subseteq_{I}^{}$ G gilt: $\chi$(H) = $\omega$(H)

Satz: (weak) perfekt graph theorem (Berge 1960 -- Lovasz, 1971) G perfekt $\iff$ $\overline{G}$ perfekt

Satz: (strong) perfect graph theorem (-- Robertson, Seymour, 2003) G perfekt $\iff$ G enthält keinen induzierten C₅, C₇, C₉,...,$\overline{C_5}$,$\overline{C_7}$,$\overline{C_9}$,....