Book:Reinhard Diestel/Graph Theory/Third Edition

Reinhard Diestel: Graph Theory (3rd Edition)

Published $\text {2005}$, 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, Covering and Packing

2.1 Matching in bipartite graphs*

2.2 Matching in general graphs'*'

2.3 Packing and covering

2.4 Tree-packing and arboricity

2.5 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 Linking 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. Extremal Graph Theory

7.1 Subgraphs*

7.2 Minors'*'

7.3 Hadwiger's conjecture*

7.4 Szemeredi's regularity lemma

7.5 Applying the regularity lemma

Exercises

Notes

8. Infinite Graphs

8.1 Basic notions, facts and techniques*

8.2 Paths, trees, and ends'*'

8.3 Homogeneous and universal graphs*

8.4 Connectivity and matching

8.5 The topological end space

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

A. Infinite sets

B. Surfaces

Hints for all the exercises

Index

Symbol index