Graph Theory

Second Edition
Contents
1. The Basics

1.1 Graphs ....................................... 2
1.2 The degree of a vertex ....................... 4
1.3 Paths and cycles ............................. 6
1.4 Connectivity ................................. 9
1.5 Trees and forests ............................ 12
1.6 Bipartite graphs ............................. 14
1.7 Contraction and minors ....................... 16
1.8 Euler tours .................................. 18
1.9 Some linear algebra .......................... 20
1.10 Other notions of graphs ...................... 25
Exercises .................................... 26
Notes ........................................ 28
2. Matching

2.1 Matching in bipartite graphs ................. 29
2.2 Matching in general graphs ................... 34
2.3 Path covers .................................. 39
Exercises .................................... 40
Notes ........................................ 42
3. Connectivity

3.1 2-Connected graphs and subgraphs ............. 43
3.2 The structure of 3-connected graphs........... 45
3.3 Menger's theorem ............................. 50
3.4 Mader's theorem .............................. 56
3.5 Edge-disjoint spanning trees ................. 58
3.6 Paths between given pairs of vertices ........ 61
Exercises .................................... 63
Notes ........................................ 65
4. Planar Graphs

4.1 Topological prerequisites .................... 68
4.2 Plane graphs ................................. 70
4.3 Drawings ..................................... 76
4.4 Planar graphs: Kuratowski's theorem .......... 80
4.5 Algebraic planarity criteria ................. 85
4.6 Plane duality ................................ 87
Exercises .................................... 89
Notes ........................................ 92
5. Colouring

5.1 Colouring maps and planar graphs ............. 96
5.2 Colouring vertices ........................... 98
5.3 Colouring edges .............................. 103
5.4 List colouring ............................... 105
5.5 Perfect graphs ............................... 110
Exercises .................................... 117
Notes ........................................ 120

6. Flows

6.1 Circulations ................................. 124
6.2 Flows in networks ............................ 125
6.3 Group-valued flows ........................... 128
6.4 k-Flows for small k .......................... 133
6.5 Flow-colouring duality ....................... 136
6.6 Tutte's flow conjectures ..................... 140
Exercises .................................... 144
Notes ........................................ 145
7. Substructures in Dense Graphs

7.1 Subgraphs .................................... 148
7.2 Szemerédi's regularity lemma ................. 153
7.3 Applying the regularity lemma ................ 160
Exercises .................................... 165
Notes ........................................ 166
8. Substructures in Sparse Graphs

8.1 Topological minors ........................... 170
8.2 Minors ....................................... 179
8.3 Hadwiger's conjecture ........................ 181
Exercises .................................... 184
Notes ........................................ 186
9. Ramsey Theory for Graphs

9.1 Ramsey's original theorems ................... 190
9.2 Ramsey numbers ............................... 193
9.3 Induced Ramsey theorems ...................... 197
9.4 Ramsey properties and connectivity ........... 207
Exercises .................................... 208
Notes ........................................ 210
10. Hamilton Cycles

10.1 Simple sufficient conditions ................. 213
10.2 Hamilton cycles and degree sequence .......... 216
10.3 Hamilton cycles in the square of a graph ..... 218
Exercises .................................... 226
Notes ........................................ 227
11. Random Graphs

11.1 The notion of a random graph ................. 230
11.2 The probabilistic method ..................... 235
11.3 Properties of almost all graphs .............. 238
11.4 Threshold functions and second moments ....... 242
Exercises .................................... 247
Notes ........................................ 249
12. Minors, Trees, and WQO

12.1 Well-quasi-ordering .......................... 251
12.2 The minor theorem for trees .................. 253
12.3 Tree-decompositions .......................... 255
12.4 Tree-width and forbidden minors .............. 263
12.5 The graph minor theorem ...................... 274
Exercises .................................... 277
Notes ........................................ 280

Hints for all the exercises ............................ 283
Index .................................................. 299
Symbol index ........................................... 311

Another Core Of Computer Science Books
Download