Perfect elimination schemes

Def: Anordnung [v₁, v₂,..., v_n] von V(G) heißt Abpflück-Ordnung (perfect elimination scheme, PES), falls für alle i: v_i ist simplizial in G{v_i,..., v_n}.

Satz: G chordal $\iff$ G besitzt PES.

sogar Satz: solches PES kann mit beliebigem simplizialen Knoten beginnen.

Dieses PES definiert auf G eine Baumstruktur, diese kann man algorithmisch ausnutzen.

Z. B. kann man $\omega$(G) und $\chi$(G) für chordale G leicht bestimmen

(viel leichter als für allgemeine Graphen)