Übungsblatt 6: Lösung

\(n = n(G) +- n(\bar{G}), m = m(G), \bar{m} = M(\bar{G})\)

Angenommen, \(\bar{G}\) planar, dann \(m \leq 3n - 6\) und \[ \frac{n(n-1)}{2} - 3n + 6 \leq \frac{n(n-1)}{2} - m = \bar{m} \leq 3n - 6 \]

\(\Rightarrow 24 \leq n(13 - n)\), was für \(n \geq 11\) nicht erfüllt ist. Widerspruch.

  1. Kontraktion der Kanten liefert einen \(K_5\)-Minor und deswegen ist \(G_1\) nicht planar.

  2. \(G_2\) ist einbettbar durch

  3. Die Kontraktion von \(G_3\) liefert einen \(K_{3,3}\)-Minor:

Nach VL: \(m \leq 3n - 6\) und \(n = \sum_{i=3}^\Delta n_i\)

Nach handschaking Lemma: \(2m = \sum_{i=3}^\Delta i n_i\)

\(\Rightarrow \sum_{i=3}^\Delta i n_i = 2m \leq 6n - 12 = 6 \sum_{i=3}^\Delta n_i -12\) \(\Rightarrow n_5 + 2n_4 + 3n_3 \leq 12 + n_7 + 2n_8 - 3n_9 + \ldots + (\Delta - 6)n_\Delta\) \(\Rightarrow 3(n_5 + n_4 + n_3) \geq n_5 + 2n_4 + 3n_3 \geq 12\) \(\Rightarrow n_5 + n_4 + n_3 \geq 4\)

Sei \(M := max…\). - \(G_i \subseteq G_1\) für alle \(i = 1,\ldots,n\). Also ist \(deg(G_1) \geq M\) - Sei \(H \subseteq G\), sodass \(\delta(H) = deg(G_1)\) und sei \(i \in \{1, \ldots, n\}\), sodass \(H \subseteq G_i\), aber \(H\nsubseteq G_{i+1}\).

Dann folgt \(v_i \in H\), also \[ deg(G_1) = \delta(H) \leq d_H(v_i) \leq d_{G_i}(v_i) = \delta(G_i) \leq M \] Insgesamt folgt also \(deg(G_1) \leq M\).

  1. Seien \(c_G: V(G) \rightarrow \{1, \ldots, \chi(G)\}\) und \(c_G: V(H) \rightarrow \{1, \ldots, \chi(H)\}\) Knotenfärbungen von G und H.

Definiere Färbung c von \(G \cup H\) durch \(c(v) = (c_G(v), c_H(v))\) für alle \(v \in V(G \cup H) = V(G) = V(H)\).

Wenn \(vw \in E(G)\), dann gilt \(c_G(v) \neq c_G(w)\). Also \(c(v) \neq c(w)\).

Wenn \(vw \in E(H)\), dann analog \(c(v) \neq c(w)\).

Also ist c eine Knotenfärbung von \(G \cup H\) mit max. \(\chi(G) \chi(H)\) Farben. Also \[ \chi(G \cup H) \leq \chi(G) \chi(H). \]

  1. Wenn \(G \cong \bar{G}^*\), dann \[ n = \chi(K_n) = \chi(G \cup \bar{G}) \leq \chi(G) \chi(\bar{G}) = \chi(G)^2 \] Also ist \([\sqrt{n}] \leq \chi(G)\).

  2. \(G = P_4\) oder \(G=C_5\) erfüllen die letzte Ungleichung mit Gleichheit.

Definition

Graphen G mit \(\chi(G) = k\) und der Eigenschaft, dass \(\chi(H) < k\) für alle echten Teilgraphen \(H \subsetneq G\), heißen k-kritisch.

Aufgabe: Alle 3-kritischen Graphen bis auf Isomorphie bestimmen.

Beweis

Zunächst klar, dass jeder ungerade Kreis ist 3-kritisch.

Bipartite Graphen haben chromatische Zahl \(\leq 2\), also ist G wegen \(\chi(G) = 3\) nicht bipartit.

Sei jetzt G 3-kritisch. Dann enthält G einen ungeraden Kreis C.

Gäbe ein \(v \in V(G) \setminus V(C)\) oder \(e \in E(G) \setminus E(C)\), dann wäre C auch in \(G-v\) bzw. \(G-e\) enthalten. Also folgt \(\chi(G-v) \geq 3\) bzw. \(\chi(G-e) \geq 3\) im Widerspruch dazu, dass G 3-kritisch ist. Also ist \(G = C_{2k+1}, k \in \N\).

Definition

Sei \(G\) ein Graph. Eine Familie \(\{A_1,\dots,A_k\}\) heißt Cliquen-Überdeckung von \(G\), wenn \(V(G)=A_1\cup\cdots\cup A_k\) eine Partition von \(V(G)\) ist und jeder induzierte Teilgraph \(G[A_i]\) eine Clique ist. Die minimale Anzahl der Teilmengen in einer Cliquen-Überdeckung nennt man Cliquen-Überdeckungszahl \(\theta(G)\).

Beh: Für jeden Graphen \(G\) gilt \(\chi(\overline G)=\theta(G)\,.\)

Die Menge \(\{A_1, \ldots, A_k\}\) partitioniert G in Cliquen genau dann, wenn sie \(\bar{G}\) in unabhänngige Mengen partitioniert.

Also ist die minimale Größe einer solchen Partition in G gleich \(\theta(G)\) und in \(\bar{G}\) gleich \(\chi{(\bar{G})}\).

  1. Zuerst sei G bipartit und r-regulär. Nach Übungsblatt 5, Aufgabe 4 ist G 1-faktorisierbar Nutzen wir jeden 1-Faktor als Farbklasse und erhalten wir eine r-Kantenfärbung von G. Damit ist \(\chi^\prime(G) \leq r\). und nach Vizing folgt auch \(\chi^\prime(G) \geq r\).

  2. Jetzt sei G bipartit mit der Partitionsmengen \[ A = \{a_1, \ldots, a_k\}, B = \{b_1, \ldots, b_l\} \] Wenn \(\delta(G) = \Delta(G)\), dann sind wir fertig. Sei also \(\delta(G) < \Delta(G)\).

Setze \(A^\prime = \{a_1^\prime, \ldots, a_k^\prime\}, B^\prime = \{b_1^\prime, \ldots, b_l^\prime\}\). Konstruiere ein bipartiten Graphen H mit \(G \subseteq H\). Die Bipartitionen von H sind \(A \cup B^\prime\) und \(B \cup A^\prime\).

Für jede Kante \(a_ib_j\) in G enthält H die Kanten \(a_ib_j\) und \(a_i^\prime b_j^\prime\). Für jeden Knoten \(a_i\) und \(b_j\) in G mit \(d_G(a_i) < \Delta(G)\) bzw. \(d_G(b_j) < \Delta(G)\) enthält H die Kante \(a_ia_i^\prime\) bzw. \(b_j b_j^\prime\).

Dann gilt \(G \subseteq H, \Delta(G) = \Delta(G), \delta(H) = \delta(G) + 1\).

Falls \(\delta(G) < \Delta(H)\) wiederhole die Konstruktion insgesamt \((\Delta(G) - \delta(H))\) mal um endlich \(\Delta(G)\)-regulären, bipartiten Graphen \(\bar{H}\) mit \(G \subseteq \bar{H}\) zu erhalten. Damit \[ \Delta(G) \leq \chi(G) \leq \chi(\bar{H}) = \Delta(\bar{H}) = \Delta(G). \]