Chromatic Graph Theory Book

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