Four-Color Problem (eBook)

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