5 Bipartite Graphen

Definition 5.1 (Multipartite Graphen)

Ein Graph \(G=(V,E)\) heißt \(r\)-partit, wenn \(V\) in \(r\) disjunkte Klassen \(V_1,\dots,V_r\) partitioniert werden kann, sodass jede Kante ihre Endpunkte in unterschiedlichen Klassen hat (d.h. in derselben Klasse sind keine zwei Knoten benachbart).
Für \(r=2\) nennen wir \(G\) bipartit, für \(r=3\) ist tripartit.
Bei bipartiten Graphen schreibt man \(G=(V_1\cup V_2,E)\) mit \(V_1\cap V_2=\varnothing\), sodass jede Kante \(\{i,j\}\in E\) erfüllt: \(i\in V_1\) und \(j\in V_2\).
Die Partition \(V_1,\dots,V_r\) nennt man auch die Farbklassen von \(G\).

Bemerkung

Ein Graph G ist genau dann 1-partit, wenn G kantenlos ist.
Jeder Graph G ist n(G)-partit.
Jeder \(k\)-partite Graph ist auch immer \(l\)-partit für \(l \in [k,…,n(G)]\).
Die kleinste solche Zahl heißt die chromatische Zahl (siehe mehr dafür in section 12).

Definition 5.2

Ein \(r\)-partiter Graph, in dem jede Kante zwischen zwei verschiedenen Farbklassen liegt, heißt vollständig.
Die vollständigen \(r\)-partiten Graphen bezeichnet man mit \(K_{n_1,\dots,n_r}\) bzw. \(K_r^s\) für \(n_1=\dots=n_r=s\).

Proposition 5.3

Ein Graph ist bipartit genau dann, wenn er keinen Kreis ungerader Länge enthält. D.h. \[\forall U \subseteq V(G) : G[U] \cong C_n \implies n \in 4 + 2\N_0\]

Beweis

(\(\Rightarrow\)) Wenn \(G\) bipartit ist, hat jeder Kreis gerade Länge, da die Knoten alternierend aus \(V_1\) und \(V_2\) stammen.

(\(\Leftarrow\)) Sei \(G=(V,E)\) ein Graph ohne Kreise ungerader Länge. OBdA nehmen wir an, \(G\) sei zusammenhängend. Wähle einen Spannbaum \(T\subseteq G\) und fixiere eine beliebige Wurzel. Wir definieren
\[V_1=\{v\in V:\text{Tiefe}(v)\text{ ist gerade}\},\quad V_2=\{v\in V:\text{Tiefe}(v)\text{ ist ungerade}\}.\]
Da \(T\) ein Spannbaum ist, schließt jede Kante \(\{i,j\}\in E\setminus T\) nach Theorem 4.3 einen Kreis. Weil alle Kreise gerade sein müssen, ist der zugehörige \(i\)-\(j\)-Weg im Baum ungerader Länge, also liegen \(i\) und \(j\) in verschiedenen Farblassen. Daher ist \(G\) bipartit.

Korollar 5.4

Jeder azyklischer Graph ist bipartit.
Ist \(G\) bipartit mit \(|E|\ge1\), so ist die Cliquenzahl \(\omega(G)=2\).

Lemma 5.5

Ist \(G\) r-partit, dann ist die Cliquenzahl \(\omega(G)\le r\).

Beweis

Da \(G\) \(r\)-partit ist, existiert eine Partition \(V=V_1\cup\cdots\cup V_r\) in stabile Mengen. Eine Clique kann höchstens einen Knoten aus jeder stabilen Menge wählen, also ist ihre Größe \(\le r\).

Lemma 5.6

Ist \(G\) \(r\)-partit mit Partition \(V_1,\dots,V_r\), dann
\[\alpha(G)\ge \max_{1\le i\le r}|V_i|.\]

Beweis

Jede Farbklasse \(V_i\) ist per Definition unabhängig, daher gilt \(\alpha(G)\ge\max_i|V_i|\).