Graph Theory - Graduate Texts in Mathematics
Description
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
More details
Content
2 - Preface [Seite 4]
2.1 - About the second edition [Seite 7]
2.2 - About the third edition [Seite 8]
2.3 - About the fourth edition [Seite 10]
2.4 - About the fifth edition [Seite 11]
3 - Contents [Seite 12]
4 - 1. The Basics [Seite 16]
4.1 - 1.1 Graphs [Seite 17]
4.2 - 1.2 The degree of a vertex [Seite 20]
4.3 - 1.3 Paths and cycles [Seite 21]
4.4 - 1.4 Connectivity [Seite 25]
4.5 - 1.5 Trees and forests [Seite 28]
4.6 - 1.6 Bipartite graphs [Seite 32]
4.7 - 1.7 Contraction and minors [Seite 34]
4.8 - 1.8 Euler tours [Seite 37]
4.9 - 1.9 Some linear algebra [Seite 38]
4.10 - 1.10 Other notions of graphs [Seite 42]
4.11 - Exercises [Seite 45]
4.12 - Notes [Seite 48]
5 - 2. Matching, Covering and Packing [Seite 50]
5.1 - 2.1 Matching in bipartite graphs [Seite 51]
5.2 - 2.2 Matching in general graphs [Seite 56]
5.3 - 2.3 The Erdös-Pósa theorem [Seite 60]
5.4 - 2.4 Tree packing and arboricity [Seite 63]
5.5 - 2.5 Path covers [Seite 67]
5.6 - Exercises [Seite 68]
5.7 - Notes [Seite 71]
6 - 3. Connectivity [Seite 74]
6.1 - 3.1 2-Connected graphs and subgraphs [Seite 74]
6.2 - 3.2 The structure of 3-connected graphs [Seite 77]
6.3 - 3.3 Menger's theorem [Seite 82]
6.4 - 3.4 Mader's theorem [Seite 87]
6.5 - 3.5 Linking pairs of vertices [Seite 89]
6.6 - Exercises [Seite 97]
6.7 - Notes [Seite 100]
7 - 4. Planar Graphs [Seite 104]
7.1 - 4.1 Topological prerequisites [Seite 105]
7.2 - 4.2 Plane graphs [Seite 107]
7.3 - 4.3 Drawings [Seite 113]
7.4 - 4.4 Planar graphs: Kuratowski's theorem [Seite 117]
7.5 - 4.5 Algebraic planarity criteria [Seite 122]
7.6 - 4.6 Plane duality [Seite 125]
7.7 - Exercises [Seite 128]
7.8 - Notes [Seite 132]
8 - 5. Colouring [Seite 134]
8.1 - 5.1 Colouring maps and planar graphs [Seite 135]
8.2 - 5.2 Colouring vertices [Seite 137]
8.3 - 5.3 Colouring edges [Seite 142]
8.4 - 5.4 List colouring [Seite 144]
8.5 - 5.5 Perfect graphs [Seite 150]
8.6 - Exercises [Seite 157]
8.7 - Notes [Seite 161]
9 - 6. Flows [Seite 164]
9.1 - 6.1 Circulations [Seite 165]
9.2 - 6.2 Flows in networks [Seite 166]
9.3 - 6.3 Group-valued flows [Seite 169]
9.4 - 6.4 k-Flows for small k [Seite 174]
9.5 - 6.5 Flow-colouring duality [Seite 177]
9.6 - 6.6 Tutte's flow conjectures [Seite 180]
9.7 - Exercises [Seite 184]
9.8 - Notes [Seite 186]
10 - 7. Extremal Graph Theory [Seite 188]
10.1 - 7.1 Subgraphs [Seite 189]
10.2 - 7.2 Minors [Seite 195]
10.3 - 7.3 Hadwiger's conjecture [Seite 198]
10.4 - 7.4 Szemerédi's regularity lemma [Seite 202]
10.5 - 7.5 Applying the regularity lemma [Seite 210]
10.6 - Exercises [Seite 216]
10.7 - Notes [Seite 219]
11 - 8. Infinite Graphs [Seite 224]
11.1 - 8.1 Basic notions, facts and techniques [Seite 225]
11.2 - 8.2 Paths, trees, and ends [Seite 234]
11.3 - 8.3 Homogeneous and universal graphs [Seite 243]
11.4 - 8.4 Connectivity and matching [Seite 246]
11.5 - 8.5 Recursive structures [Seite 257]
11.6 - 8.6 Graphs with ends: the complete picture [Seite 260]
11.7 - 8.7 The topological cycle space [Seite 269]
11.8 - 8.8 Infinite graphs as limits of finite ones [Seite 273]
11.9 - Exercises [Seite 276]
11.10 - Notes [Seite 288]
12 - 9. Ramsey Theory for Graphs [Seite 298]
12.1 - 9.1 Ramsey's original theorems [Seite 299]
12.2 - 9.2 Ramsey numbers [Seite 302]
12.3 - 9.3 Induced Ramsey theorems [Seite 305]
12.4 - 9.4 Ramsey properties and connectivity [Seite 315]
12.5 - Exercises [Seite 318]
12.6 - Notes [Seite 319]
13 - 10. Hamilton Cycles [Seite 322]
13.1 - 10.1 Sufficient conditions [Seite 322]
13.2 - 10.2 Hamilton cycles and degree sequences [Seite 326]
13.3 - 10.3 Hamilton cycles in the square of a graph [Seite 329]
13.4 - Exercises [Seite 334]
13.5 - Notes [Seite 335]
14 - 11. Random Graphs [Seite 338]
14.1 - 11.1 The notion of a random graph [Seite 339]
14.2 - 11.2 The probabilistic method [Seite 344]
14.3 - 11.3 Properties of almost all graphs [Seite 347]
14.4 - 11.4 Threshold functions and second moments [Seite 350]
14.5 - Exercises [Seite 357]
14.6 - Notes [Seite 359]
15 - 12. Minors, Trees, and WQO [Seite 362]
15.1 - 12.1 Well-quasi-ordering [Seite 363]
15.2 - 12.2 The graph minor theorem for trees [Seite 364]
15.3 - 12.3 Tree-decompositions [Seite 366]
15.4 - 12.4 Tree-width [Seite 370]
15.5 - 12.5 Tangles [Seite 375]
15.6 - 12.6 Tree-decompositions and forbidden minors [Seite 384]
15.7 - 12.7 The graph minor theorem [Seite 389]
15.8 - Exercises [Seite 397]
15.9 - Notes [Seite 403]
16 - Appendix A: Infinite sets [Seite 408]
17 - Appendix B: Surfaces [Seite 414]
18 - Hints for the Exercises [Seite 422]
19 - Index [Seite 424]
20 - Symbol Index [Seite 442]
