K-partiter Graph
# K-partiter Graph

Ein $k$-partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für $k=2$ heißen diese Graphen bipartite Graphen.

## Definitionen

Eine k-Partition eines Graphen $G=(V,E)$ ist eine Zerlegung der Knotenmenge $V$ in $k$ disjunkte Teilmengen $V_{1},\ldots ,V_{k}$, sodass keine adjazenten Knoten in der gleichen Menge $V_{i}$ liegen, das heißt
    $\forall i\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{i}\rightarrow \{v,w\}\not \in E$.
Man beachte, dass eine solche k-Partition nicht eindeutig ist. Es ist durchaus möglich, dass es mehrere k-Partitionen gibt, die diese Eigenschaft erfüllen. Ein Graph heißt nun k-partit, falls er eine k-Partition besitzt. Man nennt den Graphen vollständig k-partit, falls außerdem jeder Knoten mit allen Knoten aller anderen k-Partitionen verbunden ist, wenn also gilt:
    $\forall i\neq j\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{j}\rightarrow \{v,w\}\in E$.
Mit $K_{n_{1},\ldots ,n_{k}}$ notiert man einen vollständig k-partiten Graphen, mit $|V_{i}|=n_{i}$.

## Beispiel Turán-Graph

Die Turán-Graphen $T_{m}(n)$ ($3\leq m<n$) sind vollständige $m$-partite Graphen. Das nebenstehende Beispiel $T_{3}(7)$ ist 3-partit. Bezeichnet $\lfloor \cdot \rfloor$ die Floor-Funktion, so ist
    $T_{m}(n)=K_{\lfloor {\frac {n}{m}}\rfloor ,\lfloor {\frac {n+1}{m}}\rfloor ,\ldots ,\lfloor {\frac {n+m-1}{m}}\rfloor }$.
Für das nebenstehende Beispiel gilt damit
    $T_{3}(7)=K_{2,2,3}$.

## Eigenschaften

* Jeder k-partite Graph ist k-knotenfärbbar. Dabei wird jeder Partitionsklasse eine Farbe zugewiesen. Die Frage, ob ein Graph k-partit ist, ist also äquivalent zu der Frage, ob der Graph k-knotenfärbbar ist. Die chromatische Zahl eines Graphen $G$ ist somit das kleinste $k$, sodass $G$ eine k-Partition besitzt.
* Jeder k-partite Graph ist auch immer ein k+x-partiter Graph, wobei x eine natürliche Zahl und k+x kleiner als die Knotenzahl ist.
* Ein vollständig k-partiter Graph $K_{n_{1},\ldots ,n_{k}}$ mit $n_{1}\leq \ldots \leq n_{k}$ besitzt immer ein Matching der Größe $\min\{\sum _{i=1}^{k-1}n_{i},\lfloor {\frac {1}{2}}\sum _{i=1}^{k}n_{i}\rfloor \}$, welches effizient berechnet werden kann.