Übung 8 1− . Versuche, den Beweis des Fünffarbensatzes in einen Beweis des Vierfarbensatzes umzuwandeln, wie folgt. Definiere v und H wie gehabt, nimm induktiv an, dass H eine 4-Färbung habe, und folge dann wieder dem Beweis des Fünffarbensatzes. Wo geht dies schief? 2. Leite die chromatische Zahl eines Graphen aus den chromatischen Zahlen seiner Blöcke her. 3. Zeige, dass in einem maximal plättbaren Graphen mit mindestens 6 Ecken jede zusätzliche Kante sowohl einen T K 5 als auch einen T K3,3 entstehen lässt. 4. Ein Graph heißt outerplanar , wenn er eine Zeichnung besitzt, bei der alle Ecken auf dem Rand des Außengebiets liegen. Zeige, dass ein Graph genau dann outerplanar ist, wenn er weder K 4 noch K2,3 als Minor enthält. 5+ . Zeige, dass es zu jedem k ∈ N einen k-chromatischen Graphen gibt, der kein Dreieck enthält. 6+ . Zeige die Gleichwertigkeit der folgenden Aussagen über Graphen G: (i) χ(G) ≤ k; (ii) G hat eine Orientierung, in der kein gerichteter Weg die Länge k hat; (iii) G hat eine Orientierung wie in (ii), in der es auch keine gerichteten Kreise gibt. 1 Hinweise 1− . Wo im Beweis des Fünffarbensatzes wird benutzt, dass v höchstens so viele Nachbarn hat, wie es Farben gibt? 2. Wie können die Färbungen verschiedener Blöcke einander beeinflussen? 3. Benutze, dass jeder maximal plättbare Graph 3-zusammenhängend ist (siehe Korollar 3.4.7 im Buch), und dass die Nachbarn jeder Ecke einen Kreis induzieren. 4. Simuliere die Outerplanarität durch eine geeignete Modifikation des betrachteten Graphen G. 5+ . Induktion nach k. Beim Induktionsschritt k → k + 1 könnte es helfen, mehr als ein Exemplar des Graphen für k zu verwenden. 6+ . Zur Implikation (ii)→(i) betrachte einen maximalen gerichteten Teilgraphen D der gegebenen Orientierung von G, der keinen gerichteten Kreis enthält. Benutze die Annahme, dass es in D keine langen gerichteten Wege gibt, zur Konstruktion einer k-Färbung des D zugrundeliegenden ungerichteten Graphen. Zeige dann, dass dies auch eine k-Färbung von G ist. 2