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 C5, C7, C9,...,$ \overline{C_5}$,$ \overline{C_7}$,$ \overline{C_9}$,....



Johannes Waldmann 2005-01-25