Graph Theory - Graduate Texts in Mathematics (eBook)

5th edition (2016)

Reinhard Diestel (Autor)

eBook Download: PDF

2024 | 6. Auflage
444 Seiten
Springer-Diestel (Verlag)
978-3-96134-005-7 (ISBN)

Infos

This standard textbook on modern graph theory combines the authority of a classic with the engaging freshness of style that is the hallmark of active mathematics. It covers the core material of the subject, with concise yet complete proofs, while offering glimpses of more advanced methods in each field via one or two deeper results.

This is a major new edition. Among many other improvements, it offers additional tools for applying the regularity lemma, brings the tangle theory of graph minors up to the cutting edge of current research, and addresses new topics such as chi-boundedness in perfect graph theory.

The book can be used as a reliable text for an introductory graduate course and is also suitable for self-study.

From the reviews:

“Deep, clear, wonderful. This is a serious book about the heart of graph theory. It has depth and integrity.” Persi Diaconis & Ron Graham, SIAM Review

“The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theory.” Bulletin of the Institute of Combinatorics and its Applications

“Succeeds dramatically ... a hell of a good book.” MAA Reviews

“ ... like listening to someone explain mathematics.” Bulletin of the AMS

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 6.9.2024
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 3-96134-005-6 / 3961340056
• ISBN-13: 978-3-96134-005-7 / 9783961340057