The Four-Color Problem

The Problem Four-Color, Volume 27......Page 6
Copyright Page......Page 7
Contents......Page 14
Preface......Page 8
Introduction......Page 12
1.1. Planar Representations......Page 18
1.2. The Faces......Page 19
1.3. Maximal Planar Graphs. Straight Line Representations......Page 22
2.1. Bridges in General Graphs......Page 29
2.2. Circuit Bridges......Page 30
2.3. Equivalence of Planar Representations......Page 33
2.4. Uniqueness of Representations......Page 35
2.5. Transfer of Bridges......Page 36
2.6. Characterization of Planar Graphs......Page 38
2.7. Further Observations on Maximal Graphs......Page 42
3.1. Geometric Definition of Duality......Page 47
3.2. Observations on Graphs and Their Duals......Page 50
3.3. Relational Definition of Duality......Page 53
3.4. Characterization of Planar Graphs......Page 58
3.5. Maximal Bipartite Graphs. Self-Dual Graphs......Page 61
4.1. Euler's Formula......Page 65
4.2. Regular Graphs......Page 69
4.3. The Euler Contributions......Page 71
5.1. Circuit Arcs......Page 79
5.2. Hamilton Circuits......Page 85
6.1. Types of Coloration......Page 92
6.2. Two Colors......Page 94
6.3. Reductions......Page 95
6.4. The Five-Color Theorem......Page 101
6.5. TheTheorem of Brooks......Page 104
7.1. Vertex Coloration......Page 107
7.2. The Dual Theory......Page 109
7.3. Color Directed Graphs......Page 111
7.4. Some Special Applications......Page 115
8.1. Decomposition into Three Subgraphs......Page 119
8.2. Bipartite Dichotomy......Page 121
8.3. Even Subgraphs......Page 122
8.4. Graphs with Small Face Boundaries......Page 125
8.5. Angle Characters and Congruence Conditions (mod 3)......Page 129
9.1. Color Reduction to Cubic Graphs......Page 134
9.2. Configurations in Cubic Graphs......Page 136
9.3. Four-Color Conditions in Cubic Graphs......Page 138
9.4. The Interchange Graph and the Color Problems......Page 141
9.5. Planar Interchange Graphs......Page 144
9.6. Construction of Cubic Graphs......Page 146
10.1. Contractions and Subcontractions......Page 151
10.2. Maximal Graphs and Simplex Decompositions......Page 155
10.3. lndecomposable Graphs......Page 160
10.4. Hadwiger’s Conjecture......Page 163
10.5. Wagner’s Equivalence Theorem......Page 170
10.6. Contractions to S4......Page 175
10.7. Multiply-Connected Graphs......Page 177
11.1. Types of Critical Graphs......Page 181
11.2. Contraction Critical Graphs......Page 184
11.3. Edge-Critical Graphs......Page 188
11. 4. Construction of e-Critical Graphs......Page 192
11.5. Conjunctions and Mergers......Page 197
11.6. Amalgamations......Page 200
11. 7. Mergers of Simplexes......Page 203
12.1. Separations......Page 209
12.2. Irreducible Graphs......Page 213
12.3. Reductions for Minor Vertices......Page 215
12.4. Errera Circuits and 5-Components......Page 227
12.5. Lower Bounds for Irreducible Graphs......Page 232
13.1. Formulations of the Three-Color Problem......Page 242
13.2. The Theorem of Grötzsch......Page 246
14.1. General Observations......Page 256
14.2. Coloration of an Augmented Graph......Page 258
14.3. The Theorem ofShannon......Page 260
14.4. The Theorem of Vizing......Page 262
Bibliography......Page 266
Author Index......Page 272
Subject Index......Page 274