Book:Reinhard Diestel/Graph Theory/Second Edition

Reinhard Diestel: Graph Theory (2nd Edition)

Published $\text {2000}$, Springer

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

Subject Matter

• Graph Theory

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