Graph Theory

Preface......Page 2
About the second edition......Page 5
About the third edition......Page 6
Contents......Page 8
1. The Basics......Page 12
1.1 Graphs......Page 13
1.2 The degree of a vertex......Page 16
1.3 Paths and cycles......Page 17
1.4 Connectivity......Page 21
1.5 Trees and forests......Page 24
1.6 Bipartite graphs......Page 28
1.7 Contraction and minors......Page 29
1.8 Euler tours......Page 32
1.9 Some linear algebra......Page 34
1.10 Other notions of graphs......Page 39
Exercises......Page 41
Notes......Page 43
2. Matching Covering and Packing......Page 44
2.1 Matching in bipartite graphs......Page 45
2.2 Matching in general graphs......Page 50
2.3 Packing and covering......Page 55
2.4 Tree-packing and arboricity......Page 57
2.5 Path covers......Page 60
Exercises......Page 62
Notes......Page 64
3.1 2-Connected graphs and subgraphs......Page 66
3.2 The structure of 3-connected graphs......Page 68
3.3 Menger’s theorem......Page 73
3.4 Mader’s theorem......Page 78
3.5 Linking pairs of vertices......Page 80
Exercises......Page 89
Notes......Page 91
4. Planar Graphs......Page 94
4.1 Topological prerequisites......Page 95
4.2 Plane graphs......Page 97
4.3 Drawings......Page 103
4.4 Planar graphs: Kuratowski’s theorem......Page 107
4.5 Algebraic planarity criteria......Page 112
4.6 Plane duality......Page 114
Exercises......Page 117
Notes......Page 120
5. Colouring......Page 122
5.1 Colouring maps and planar graphs......Page 123
5.2 Colouring vertices......Page 125
5.3 Colouring edges......Page 130
5.4 List colouring......Page 132
5.5 Perfect graphs......Page 137
Exercises......Page 144
Notes......Page 147
6. Flows......Page 150
6.1 Circulations......Page 151
6.2 Flows in networks......Page 152
6.3 Group-valued flows......Page 155
6.4 k-Flows for small k......Page 160
6.5 Flow-colouring duality......Page 163
6.6 Tutte’s flow conjectures......Page 167
Exercises......Page 171
Notes......Page 172
7. Extremal Graph Theory......Page 174
7.1 Subgraphs......Page 175
7.2 Minors......Page 180
7.3 Hadwiger’s conjecture......Page 183
7.4 Szemeredi’s regularity lemma......Page 186
7.5 Applying the regularity lemma......Page 194
Exercises......Page 200
Notes......Page 203
8. Infinite Graphs......Page 206
8.1 Basic notions, facts and techniques......Page 207
8.2 Paths, trees, and ends......Page 215
8.3 Homogeneous and universal graphs......Page 223
8.4 Connectivity and matching......Page 227
8.5 The topological end space......Page 237
Exercises......Page 248
Notes......Page 255
9. Ramsey Theory for Graphs......Page 262
9.1 Ramsey’s original theorems......Page 263
9.2 Ramsey numbers......Page 266
9.3 Induced Ramsey theorems......Page 269
9.4 Ramsey properties and connectivity......Page 279
Exercises......Page 282
Notes......Page 283
10.1 Simple sufficient conditions......Page 286
10.2 Hamilton cycles and degree sequences......Page 289
10.3 Hamilton cycles in the square of a graph......Page 292
Exercises......Page 300
Notes......Page 301
11. Random Graphs......Page 304
11.1 The notion of a random graph......Page 305
11.2 The probabilistic method......Page 310
11.3 Properties of almost all graphs......Page 313
11.4 Threshold functions and second moments......Page 317
Exercises......Page 323
Notes......Page 324
12. Minors Trees and WQO......Page 326
12.1 Well-quasi-ordering......Page 327
12.2 The graph minor theorem for trees......Page 328
12.3 Tree-decompositions......Page 330
12.4 Tree-width and forbidden minors......Page 338
12.5 The graph minor theorem......Page 352
Exercises......Page 361
Notes......Page 365
A. Infinite sets......Page 368
B. Surfaces......Page 372
Hints for Chapter 1......Page 380
Hints for Chapter 2......Page 382
Hints for Chapter 3......Page 383
Hints for Chapter 4......Page 384
Hints for Chapter 5......Page 386
Hints for Chapter 6......Page 388
Hints for Chapter 7......Page 389
Hints for Chapter 8......Page 391
Hints for Chapter 9......Page 397
Hints for Chapter 11......Page 398
Hints for Chapter 12......Page 399
Index......Page 404
Symbol Index......Page 420
Ordering information......Page 1