Einfuehrung in die Theorie der endlichen Graphen

Titel Seite......Page 1
Copyright Seite......Page 2
Widmung......Page 3
VORWORT......Page 5
INHALTSVERZEICHNIS......Page 13
E.1. Grundlegende Definitionen und Sätze......Page 17
E.2. Duale ebene Graphen und Karten......Page 31
E.3. Normale Karten und Triangulationen......Page 35
E.4. Der Satz von Wagner über die geradlinige Darstellbarkeit schlichter ebener Graphen......Page 37
E.5. Gerade, paare und Eulersche Karten......Page 40
E.6. Über die Erzeugung Eulerscher ebener Graphen und normaler Karten......Page 45
E.7. Ein Färbungssatz für Überlagerungen......Page 50
E.8. Das Vierfarbenproblem......Page 53
Literatur zur Einleitung......Page 54
I.1. Die EuLERsche Polyederformel für ebene Graphen......Page 55
I.2. Anwendung der Eulerschen Polyederformel......Page 56
I.3. Das Problem der regulären Polyeder......Page 60
I.4. Zwei nicht-planare Graphen......Page 61
I.5. Verallgemeinerung der Eulerschen Polyederformel für beliebige geschlossene Flächen......Page 63
Literatur zu Kapitel I......Page 65
II.1.1. Einleitung......Page 66
II.1.2. Aufhebung, Einfügung, Unterteilung......Page 67
II.1.4. Vorbereitung des Beweises......Page 69
II.1.5. Der Einbettungsalgorithmus von G. Hotz......Page 72
II.1.6. Eindeutigkeitssatz......Page 73
II.1.7. Beweis der Wirksamkeit des Algorithmus von Hotz und zugleich Beweis des Satzes von Kuratowski und des Eindeutigkeitssatzes......Page 74
II.1.8. Kürzerer, indirekt geführter Beweis des Satzes von Kuratowski......Page 87
II.1.10. Bemerkung über die Einbettbarkeit von Graphen in beliebige geschlossene Flächen......Page 88
II.2. Maßzahlen für die Abweichung eines Graphen von der Planarität......Page 89
Literatur zu Kapitel II......Page 94
III.1. Einleitung......Page 97
III.2.1. Formulierung der Sätze......Page 99
III.2.2. Vorbereitung des Beweises von Satz III.4......Page 100
III.2.3. Beweis von Satz III.4 mittels vollständiger Induktion nach der Anzahl der Kanten......Page 113
III.3. Das Problem der Existenz eines Hamiltonschen Kreises für normale Karten......Page 123
Literatur zu Kapitel III......Page 130
IV. Längste Kreise in normalen Karten......Page 132
Literatur zu Kapitel IV......Page 139
V.1.1. Einleitung......Page 140
V.1.2. Der Satz von Tait......Page 143
V.1.3. Der Satz von Heawood......Page 145
V.2. Zulässige Färbung der Länder einer normalen Karte mit drei Farben......Page 154
V.3. Der Fünffarbensatz......Page 158
V.4.1. Einleitung......Page 165
V.4.2. Eine Reduktionseigenschaft normaler Karten t......Page 166
V.4.3. Über Reduktionsfiguren; Resultate von Winn, Heesch, Ore und Stemple......Page 176
V.5.1. Ein Satz von Dirac......Page 179
V.5.2. Verallgemeinerung eines Satzes von Aarts und de Groot......Page 182
V.6. Der 51-Dreiecke-Satz......Page 204
V.7.1. Verallgemeinerung eines Satzes von Szekeres und Wilf......Page 207
V.7.3. Anwendung auf planare Graphen......Page 209
V.8.1. Die Operation der Kontraktion......Page 212
V.8.2. Vergröberung eines Graphen......Page 213
V.8.3. Die Vermutung von Hadwiger......Page 214
V.9.1. Das chromatische Polynom eines Graphen......Page 215
V.9.2. Die chromatische Diskriminante......Page 219
V.9.3. Der Satz von Tutte über das „goldene Verhältnis"......Page 221
V.10.1. Einbettung von Graphen in geschlossene Flächen......Page 223
V.10.3. Der Satz und die Vermutung von Heawood......Page 225
V.10.4. Die Sätze von Ringel und von Ringel, Youngs und anderen......Page 229
V.11. Schlußbemerkung......Page 232
Literatur zu Kapitel V......Page 233
VI.2. Die Verallgemeinerung des Satzes von Grötzsch durch Grünbaum......Page 237
VI.3. Erste Reduktionen......Page 238
VI.4. Beweis von Satz VI.3 mittels Induktion nach der Anzahl der Kanten......Page 240
VI.4.1. Beseitigung trennender Drei-, Vier- und Fünfkreise......Page 242
VI.4.2. Beseitigung der Knotenpunkte der Valenz 2......Page 246
VI.4.3. Beseitigung der Vierecke......Page 247
VI.4.4. Beseitigung der Randknotenpunkte von Dreiecken, welche die Valenz 3 haben......Page 248
VI.4.5. Reduktion von $\varepsilon$-Karten......Page 250
VI.5. Über ein Problem von Grünbaum......Page 257
VI.6. Eine Anwendung des Satzes von Grötzsch-Grünbaum auf das Vierfarbenproblem......Page 259
Literatur zu Kapitel VI......Page 260
Verzeichnis der Arbeiten von H. Grötzsch zu Fragen der Graphentheorie......Page 261
Verzeichnis der Lehrbücher und Monographien über Graphentheorie......Page 262
Namenregister......Page 265
Sachregister......Page 268
Vorderdeckel......Page 273