partielle k-Bäume

Def: ein Graph heißt k-Baum, wenn er ein PES [x₁,..., x_n] besitzt, bei dem alle Cliquen die Größe k haben:

$\forall$1$\le$i < n - k : x_i hat genau k Nachbarn in G[x_i, x_{i + 1},..., x_n] (und diese bilden eine Clique).

Satz: Bäume sind 1-Bäume.

Def: ein Graph G = (V, E) heißt partieller k-Baum, falls es einen k-Baum G' = (V', E') gibt mit V = V' und E $\subseteq$ E'.

Beispiel: Kreise sind partielle 2-Bäume.