Preface | p. vii |
The Basics | p. 1 |
Graphs* | p. 2 |
The degree of a vertex* | p. 5 |
Paths and cycles* | p. 6 |
Connectivity* | p. 10 |
Trees and forests* | p. 13 |
Bipartite graphs* | p. 17 |
Contraction and minors* | p. 19 |
Euler tours* | p. 22 |
Some linear algebra | p. 23 |
Other notions of graphs | p. 28 |
Exercises | p. 30 |
Notes | p. 33 |
Matching Covering and Packing | p. 35 |
Matching in bipartite graphs* | p. 36 |
Matching in general graphs(*) | p. 41 |
Packing and covering | p. 45 |
Tree-packing and arboricity | p. 48 |
Path covers | p. 52 |
Exercises | p. 54 |
Notes | p. 56 |
Connectivity | p. 59 |
2-Connected graphs and subgraphs* | p. 59 |
The structure of 3-connected graphs(*) | p. 62 |
Menger's theorem* | p. 66 |
Mader's theorem | p. 72 |
Linking pairs of vertices(*) | p. 74 |
Exercises | p. 82 |
Notes | p. 85 |
Planar Graphs | p. 87 |
Topological prerequisites* | p. 88 |
Plane graphs* | p. 90 |
Drawings | p. 96 |
Planar graphs: Kuratowski's theorem* | p. 100 |
Algebraic planarity criteria | p. 105 |
Plane duality | p. 107 |
Exercises | p. 111 |
Notes | p. 114 |
Colouring | p. 117 |
Colouring maps and planar graphs* | p. 118 |
Colouring vertices* | p. 120 |
Colouring edges* | p. 125 |
List colouring | p. 127 |
Perfect graphs | p. 132 |
Exercises | p. 139 |
Notes | p. 143 |
Flows | p. 145 |
Circulations(*) | p. 146 |
Plows in networks* | p. 147 |
Group-valued flows | p. 150 |
k-Flows for small k | p. 155 |
Flow-colouring duality | p. 158 |
Tutte's flow conjectures | p. 161 |
Exercises | p. 165 |
Notes | p. 167 |
Extremal Graph Theory | p. 169 |
Subgraphs* | p. 170 |
Minors(*) | p. 175 |
Hadwiger's conjecture* | p. 178 |
Szemerédi's regularity lemma | p. 182 |
Applying the regularity lemma | p. 189 |
Exercises | p. 195 |
Notes | p. 198 |
Infinite Graphs | p. 203 |
Basic notions, facts and techniques* | p. 204 |
Paths, trees, and ends(*) | p. 213 |
Homogeneous and universal graphs* | p. 222 |
Connectivity and matching | p. 225 |
Graphs with ends: the topological viewpoint | p. 235 |
Recursive structures | p. 248 |
Exercises | p. 251 |
Notes | p. 261 |
Ramsey Theory for Graphs | p. 269 |
Ramsey's original theorems* | p. 270 |
Ramsey numbers(*) | p. 273 |
Induced Ramsey theorems | p. 276 |
Ramsey properties and connectivity(*) | p. 286 |
Exercises | p. 289 |
Notes | p. 290 |
Hamilton Cycles | p. 293 |
Sufficient conditions* | p. 293 |
Hamilton cycles and degree sequences* | p. 297 |
Hamilton cycles in the square of a graph | p. 300 |
Exercises | p. 305 |
Notes | p. 306 |
Random Graphs | p. 309 |
The notion of a random graph* | p. 310 |
The probabilistic method* | p. 315 |
Properties of almost all graphs* | p. 318 |
Threshold functions and second moments | p. 322 |
Exercises | p. 329 |
Notes | p. 330 |
Minors, Trees and WQO | p. 333 |
Well-quasi-ordering* | p. 334 |
The graph minor theorem for trees* | p. 335 |
Tree-decompositions | p. 337 |
Tree-width and forbidden minors | p. 345 |
The graph minor theorem(*) | p. 359 |
Exercises | p. 368 |
Notes | p. 373 |
Infinite sets | p. 377 |
Surfaces | p. 383 |
Hints for all the exercises | p. 391 |
Index | p. 419 |
Symbol index | p. 435 |
Table of Contents provided by Ingram. All Rights Reserved. |