Table of Contents
0 The Origin of Graph Colorings 1
1 Introduction to Graphs 27
1.1 Fundamental Terminology 27
1.2 Connected Graphs 30
1.3 Distance in Graphs 33
1.4 Isomorphic Graphs 37
1.5 Common Graphs and Graph Operations 39
1.6 Multigraphs and Digraphs 44
Exercises for Chapter 1 47
2 Trees and Connectivity 53
2.1 Cut-vertices, Bridges, and Blocks 53
2.2 Trees 56
2.3 Connectivity and Edge-Connectivity 59
2.4 Menger's Theorem 63
Exercises for Chapter 2 67
3 Eulerian and Hamiltonian Graphs 71
3.1 Eulerian Graphs 71
3.2 de Bruijn Digraphs 76
3.3 Hamiltonian Graphs 79
Exercises for Chapter 3 87
4 Matchings and Factorization 91
4.1 Matchings 91
4.2 Independence in Graphs 98
4.3 Factors and Factorization 100
Exercises for Chapter 4 106
5 Graph Embeddings 109
5.1 Planar Graphs and the Euler Identity 109
5.2 Hamiltonian Planar Graphs 118
5.3 Planarity Versus Nonplanarity 120
5.4 Embedding Graphs on Surfaces 131
5.5 The Graph Minor Theorem 139
Exercises for Chapter 5 141
6 Introduction to Vertex Colorings 147
6.1 The Chromatic Number of a Graph 147
6.2 Applications of Colorings 153
6.3 Perfect Graphs 160
Exercises for Chapter 6 170
7 Bounds for the Chromatic Number 175
7.1 Color-Critical Graphs 175
7.2 Upper Bounds and Greedy Colorings 179
7.3 Upper Bounds and Oriented Graphs 189
7.4 The Chromatic Number of Cartesian Products 195
Exercises for Chapter 7 200
8 Coloring Graphs on Surfaces 205
8.1 The Four Color Problem 205
8.2 The Conjectures of Hajos and Hadwiger 208
8.3 Chromatic Polynomials 211
8.4 The Heawood Map-Coloring Problem 217
Exercises for Chapter 8 219
9 Restricted Vertex Colorings 223
9.1 UniquelyColorable Graphs 223
9.2 List Colorings 230
9.3 Precoloring Extensions of Graphs 240
Exercises for Chapter 9 245
10 Edge Colorings of Graphs 249
10.1 The Chromatic Index and Vizing's Theorem 249
10.2 Class One and Class Two Graphs 255
10.3 Tait Colorings 262
10.4 Nowhere-Zero Flows 269
10.5 List Edge Colorings 279
10.6 Total Colorings of Graphs 282
Exercises for Chapter 10 284
11 Monochromatic and Rainbow Colorings 289
11.1 Ramsey Numbers 289
11.2 Turan's Theorem 296
11.3 Rainbow Ramsey Numbers 299
11.4 Rainbow Numbers of Graphs 306
11.5 Rainbow-Connected Graphs 314
11.6 The Road Coloring Problem 320
Exercises for Chapter 11 324
12 Complete Colorings 329
12.1 The Achromatic Number of a Graph 329
12.2 Graph Homomorphisms 335
12.3 The Grundy Number of a Graph 349
Exercises for Chapter 12 356
13 Distinguishing Colorings 359
13.1 Edge-Distinguishing Vertex Colorings 359
13.2 Vertex-Distinguishing Edge Colorings 370
13.3 Vertex-Distinguishing Vertex Colorings 379
13.4 Neighbor-Distinguishing Edge Colorings 385
Exercises for Chapter 13 391
14 Colorings, Distance, and Domination 397
14.1 T-Colorings 397
14.2 L(2, 1)-Colorings 403
14.3 Radio Colorings 410
14.4 Hamiltonian Colorings 417
14.5 Domination and Colorings 425
14.6 Epilogue 434
Exercises for Chapter 14 434
Appendix Study Projects 439
General References 446
Bibliography 453
Index (Names and Mathematical Terms) 465
List of Symbols 480
