5.3 Planarity Versus Nonplanarity1201315.4 Embedding Graphs on Surfaces1395.5 The Graph Minor Theorem141Exercises for Chapter 51476. Introduction to Vertex Colorings1476.1 The Chromatic Number of a Graph1536.2 Applications of Colorings1606.3 Perfect GraphsExercises for Chapter 61707. Bounds for the Chromatic Number1757.1 Color-Critical Graphs1751797.2 Upper Bounds and Greedy Colorings1897.3 Upper Bounds and Oriented Graphs1957.4 The Chromatic Number of Cartesian Products200Exercises for Chapter 72058. Coloring Graphs on Surfaces2058.1 The Four Color Problem2088.2 The Conjectures of Hajos and Hadwiger2118.3 Chromatic Polynomials8.4 The Heawood Map-Coloring Problem217219Exercises for Chapter 82239. Restricted Vertex Colorings2239.1 Uniquely Colorable Graphs2309.2 List Colorings2409.3 Precoloring Extensions of GraphsExercises for Chapter 924524910. Edge Colorings of Graphs24910.1 The Chromatic Index and Vizing's Theorem25510.2 Class One and Class Two Graphs26210.3 Tait Colorings26910.4 Nowhere-Zero Flows27910.5 List Edge Coloringsx5.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 Haj´os 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 Uniquely Colorable 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 x