Four-Color Problem (eBook)
258 Seiten
Elsevier Science (Verlag)
978-0-08-087339-8 (ISBN)
The Four-Color Problem
Front Cover 1
The Problem Four-Color, Volume 27 6
Copyright Page 7
Contents 14
Preface 8
Introduction 12
Chapter 1. Planar Graphs 18
1.1. Planar Representations 18
1.2. The Faces 19
1.3. Maximal Planar Graphs. Straight Line Representations 22
Chapter 2. Bridges and Circuits 29
2.1. Bridges in General Graphs 29
2.2. Circuit Bridges 30
2.3. Equivalence of Planar Representations 33
2.4. Uniqueness of Representations 35
2.5. Transfer of Bridges 36
2.6. Characterization of Planar Graphs 38
2.7. Further Observations on Maximal Graphs 42
Chapter 3. Dual Graphs 47
3.1. Geometric Definition of Duality 47
3.2. Observations on Graphs and Their Duals 50
3.3. Relational Definition of Duality 53
3.4. Characterization of Planar Graphs 58
3.5. Maximal Bipartite Graphs. Self-Dual Graphs 61
Chapter 4. Euler's Formula and Its Consequences 65
4.1. Euler's Formula 65
4.2. Regular Graphs 69
4.3. The Euler Contributions 71
Chapter 5. Large Circuits 79
5.1. Circuit Arcs 79
5.2. Hamilton Circuits 85
Chapter 6. Colorations 92
6.1. Types of Coloration 92
6.2. Two Colors 94
6.3. Reductions 95
6.4. The Five-Color Theorem 101
6.5. TheTheorem of Brooks 104
Chapter 7. Color Functions 107
7.1. Vertex Coloration 107
7.2. The Dual Theory 109
7.3. Color Directed Graphs 111
7.4. Some Special Applications 115
Chapter 8. Formulations of the Four-Color Problem 119
8.1. Decomposition into Three Subgraphs 119
8.2. Bipartite Dichotomy 121
8.3. Even Subgraphs 122
8.4. Graphs with Small Face Boundaries 125
8.5. Angle Characters and Congruence Conditions (mod 3) 129
Chapter 9. Cubic Graphs 134
9.1. Color Reduction to Cubic Graphs 134
9.2. Configurations in Cubic Graphs 136
9.3. Four-Color Conditions in Cubic Graphs 138
9.4. The Interchange Graph and the Color Problems 141
9.5. Planar Interchange Graphs 144
9.6. Construction of Cubic Graphs 146
Chapter 10. Hadwiger’s Conjecture 151
10.1. Contractions and Subcontractions 151
10.2. Maximal Graphs and Simplex Decompositions 155
10.3. lndecomposable Graphs 160
10.4. Hadwiger’s Conjecture 163
10.5. Wagner’s Equivalence Theorem 170
10.6. Contractions to S4 175
10.7. Multiply-Connected Graphs 177
Chapter 11. Critical Graphs 181
11.1. Types of Critical Graphs 181
11.2. Contraction Critical Graphs 184
11.3. Edge-Critical Graphs 188
11. 4. Construction of e-Critical Graphs 192
11.5. Conjunctions and Mergers 197
11.6. Amalgamations 200
11. 7. Mergers of Simplexes 203
Chapter 12. Planar 5-Chromatic Graphs 209
12.1. Separations 209
12.2. Irreducible Graphs 213
12.3. Reductions for Minor Vertices 215
12.4. Errera Circuits and 5-Components 227
12.5. Lower Bounds for Irreducible Graphs 232
Chapter 13. Three Colors 242
13.1. Formulations of the Three-Color Problem 242
13.2. The Theorem of Grötzsch 246
Chapter 14. Edge Coloration 256
14.1. General Observations 256
14.2. Coloration of an Augmented Graph 258
14.3. The Theorem ofShannon 260
14.4. The Theorem of Vizing 262
Bibliography 266
Author Index 272
Subject Index 274
Erscheint lt. Verlag | 29.8.2011 |
---|---|
Mitarbeit |
Herausgeber (Serie): Oystein Ore |
Sprache | englisch |
Themenwelt | Mathematik / Informatik ► Mathematik ► Arithmetik / Zahlentheorie |
Technik | |
ISBN-10 | 0-08-087339-1 / 0080873391 |
ISBN-13 | 978-0-08-087339-8 / 9780080873398 |
Haben Sie eine Frage zum Produkt? |
![PDF](/img/icon_pdf_big.jpg)
Größe: 9,6 MB
Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich