Book:Reinhard Diestel/Graph Theory

From ProofWiki
Jump to: navigation, search

Reinhard Diestel: Graph Theory

Published $1997$, 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. Szemeredi'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 minor theorem for trees
12.3. Tree-decompositions
12.4. Tree-width and forbidden minors
12.5. The minor theorem
Exercises
Notes


Index
Symbol index


Further Editions