Book:Reinhard Diestel/Graph Theory/Second Edition

From ProofWiki
Jump to navigation Jump to search

Reinhard Diestel: Graph Theory (2nd Edition)

Published $\text {2000}$, Springer.


This book is volume 173 of the Graduate Texts in Mathematics series.


Subject Matter


Contents

Preface
1. The Basics
1.1. Graphs
1.2. The degree of a vertex
1.3. Paths and cycles
1.4. Connectivity
1.5. Trees and forests
1.6. Bipartite graphs
1.7. Contraction and minors
1.8. Euler tours
1.9. Some linear algebra
1.10. Other notions of graphs
Exercises
Notes
2. Matching
2.1. Matching in bipartite graphs
2.2. Matching in general graphs
2.3. Path covers
Exercises
Notes
3. Connectivity
3.1. $2$-Connected graphs and subgraphs
3.2. The structure of $3$-connected graphs
3.3. Menger's theorem
3.4. Mader's theorem
3.5. Edge-disjoint spanning trees
3.6. Paths between given pairs of vertices
Exercises
Notes
4. Planar Graphs
4.1. Topological prerequisites
4.2. Plane graphs
4.3. Drawings
4.4. Planar graphs: Kuratowski's theorem
4.5. Algebraic planarity criteria
4.6. Plane duality
Exercises
Notes
5. Colouring
5.1. Colouring maps and planar graphs
5.2. Colouring vertices
5.3. Colouring edges
5.4. List colouring
5.5. Perfect graphs
Exercises
Notes
6. Flows
6.1. Circulations
6.2. Flows in networks
6.3. Group-valued flows
6.4. $k$-Flows for small $k$
6.5. Flow-colouring duality
6.6. Tutte's flow conjectures
Exercises
Notes
7. Substructures in Dense Graphs
7.1. Subgraphs
7.2. Szemer├ędi's regularity lemma
7.3. Applying the regularity lemma
Exercises
Notes
8. Substructures in Sparse Graphs
8.1. Topological minors
8.2. Minors
8.3. Hadwiger's conjecture
Exercises
Notes
9. Ramsey Theory for Graphs
9.1. Ramsey's original theorems
9.2. Ramsey numbers
9.3. Induced Ramsey theorems
9.4. Ramsey properties and connectivity
Exercises
Notes
10. Hamilton Cycles
10.1. Simple sufficient conditions
10.2. Hamilton cycles and degree sequences
10.3. Hamilton cycles in the square of a graph
Exercises
Notes
11. Random Graphs
11.1. The notion of a random graph
11.2. The probabilistic method
11.3. Properties of almost all graphs
11.4. Threshold functions and second moments
Exercises
Notes
12. Minors, Trees, and WQO
12.1. Well-quasi-ordering
12.2. The graph minor theorem for trees
12.3. Tree-decompositions
12.4. Tree-width and forbidden minors
12.5. The graph minor theorem
Exercises
Notes


Hints for all the exercises
Index
Symbol index