Search and Find
Service
Graph Theory - Graduate Texts in Mathematics - 5th edition (2016)
of: Reinhard Diestel
Springer-Diestel, 2016
ISBN: 9783961340057 , 444 Pages
5. Edition
Format: PDF, Read online
Copy protection: DRM
Title page
1
Preface
4
About the second edition
7
About the third edition
8
About the fourth edition
10
About the fifth edition
11
Contents
12
1. The Basics
16
1.1 Graphs
17
1.2 The degree of a vertex
20
1.3 Paths and cycles
21
1.4 Connectivity
25
1.5 Trees and forests
28
1.6 Bipartite graphs
32
1.7 Contraction and minors
34
1.8 Euler tours
37
1.9 Some linear algebra
38
1.10 Other notions of graphs
42
Exercises
45
Notes
48
2. Matching, Covering and Packing
50
2.1 Matching in bipartite graphs
51
2.2 Matching in general graphs
56
2.3 The Erdös-Pósa theorem
60
2.4 Tree packing and arboricity
63
2.5 Path covers
67
Exercises
68
Notes
71
3. Connectivity
74
3.1 2-Connected graphs and subgraphs
74
3.2 The structure of 3-connected graphs
77
3.3 Menger’s theorem
82
3.4 Mader’s theorem
87
3.5 Linking pairs of vertices
89
Exercises
97
Notes
100
4. Planar Graphs
104
4.1 Topological prerequisites
105
4.2 Plane graphs
107
4.3 Drawings
113
4.4 Planar graphs: Kuratowski’s theorem
117
4.5 Algebraic planarity criteria
122
4.6 Plane duality
125
Exercises
128
Notes
132
5. Colouring
134
5.1 Colouring maps and planar graphs
135
5.2 Colouring vertices
137
5.3 Colouring edges
142
5.4 List colouring
144
5.5 Perfect graphs
150
Exercises
157
Notes
161
6. Flows
164
6.1 Circulations
165
6.2 Flows in networks
166
6.3 Group-valued flows
169
6.4 k-Flows for small k
174
6.5 Flow-colouring duality
177
6.6 Tutte’s flow conjectures
180
Exercises
184
Notes
186
7. Extremal Graph Theory
188
7.1 Subgraphs
189
7.2 Minors
195
7.3 Hadwiger’s conjecture
198
7.4 Szemerédi’s regularity lemma
202
7.5 Applying the regularity lemma
210
Exercises
216
Notes
219
8. Infinite Graphs
224
8.1 Basic notions, facts and techniques
225
8.2 Paths, trees, and ends
234
8.3 Homogeneous and universal graphs
243
8.4 Connectivity and matching
246
8.5 Recursive structures
257
8.6 Graphs with ends: the complete picture
260
8.7 The topological cycle space
269
8.8 Infinite graphs as limits of finite ones
273
Exercises
276
Notes
288
9. Ramsey Theory for Graphs
298
9.1 Ramsey’s original theorems
299
9.2 Ramsey numbers
302
9.3 Induced Ramsey theorems
305
9.4 Ramsey properties and connectivity
315
Exercises
318
Notes
319
10. Hamilton Cycles
322
10.1 Sufficient conditions
322
10.2 Hamilton cycles and degree sequences
326
10.3 Hamilton cycles in the square of a graph
329
Exercises
334
Notes
335
11. Random Graphs
338
11.1 The notion of a random graph
339
11.2 The probabilistic method
344
11.3 Properties of almost all graphs
347
11.4 Threshold functions and second moments
350
Exercises
357
Notes
359
12. Minors, Trees, and WQO
362
12.1 Well-quasi-ordering
363
12.2 The graph minor theorem for trees
364
12.3 Tree-decompositions
366
12.4 Tree-width
370
12.5 Tangles
375
12.6 Tree-decompositions and forbidden minors
384
12.7 The graph minor theorem
389
Exercises
397
Notes
403
Appendix A: Infinite sets
408
Appendix B: Surfaces
414
Hints for the Exercises
422
Index
424
Symbol Index
442
All prices incl. VAT