- Standard textbook of modern graph theory
- Covers all the basic material in full detail
- Introduces and illustrates the more advanced methods of that field
This standard textbook of modern graph theory, now in its fourth edition,
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 reliably complete proofs,
while offering glimpses of more advanced methods in each field by one or two deeper
results, again with proofs given in full detail. The book can be used as a reliable text
for an introductory course, as a graduate text, and for self-study. From the reviews: This
outstanding book cannot be substituted with any other book on the present textbook market.
It has every chance of becoming the standard textbook for graph theory." Acta
Scientiarum Mathematiciarum "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 "A highlight of the book is what is by far the best
account in print of the Seymour-Robertson theory of graph minors." Mathematika "
... like listening to someone explain mathematics." Bulletin of the AMS
Table of Contents
Preface vii
1. The Basics 1
1.1 Graphs* 2
1.2 The degree of a vertex* 5
1.3 Paths and cycles*
1.4 Connectivity* 10
1.5 Trees and forests* . 13
1.6 Bipartite graphs* 17
1.7 Contraction and minors* 19
1.8 Euler tours* 22
1.9 Some linear algebra 23
1.10 Other notions of graphs 28
Exercises 30
Notes 33
2. Matching Covering and Packing 35
2.1 Matching in bipartite graphs* 36
2.2 Matching in general graphs(*) 41
2.3 Packing and covering 45
2.4 Tree-packing and arboricity 48
2.5 Path covers 52
Exercises 54
Notes 56
3. Connectivity 59
3.1 2-Connected graphs and subgraphs* 59
3.2 The structure of 3-connected graphs(*) 62
3.3 Menger’s theorem* 66
3.4 Mader’s theorem 72
3.5 Linking pairs of vertices(*) 74
Exercises 82
Notes . 85
4. Planar Graphs 87
4.1 Topological prerequisites* 88
4.2 Plane graphs* 90
4.3 Drawings 96
4.4 Planar graphs: Kuratowski’s theorem* 100
4.5 Algebraic planarity criteria 105
4.6 Plane duality 107
Exercises 111
Notes 114
5. Colouring 117
5.1 Colouring maps and planar graphs* 118
5.2 Colouring vertices* 120
5.3 Colouring edges* 125
5.4 List colouring 127
5.5 Perfect graphs 132
Exercises 139
Notes 143
6. Flows 145
6.1 Circulations(*) 146
6.2 Flows in networks* 147
6.3 Group-valued flows 150
6.4 k-Flows for small k 155
6.5 Flow-colouring duality 158
6.6 Tutte’s flow conjectures 161
Exercises 165
Notes . 167
7. Extremal Graph Theory 169
7.1 Subgraphs* . 170
7.2 Minors(*) 175
7.3 Hadwiger’s conjecture* 178
7.4 Szemer´edi’s regularity lemma 182
7.5 Applying the regularity lemma 189
Exercises 195
Notes 198
8. Infinite Graphs 203
8.1 Basic notions, facts and techniques* 204
8.2 Paths, trees, and ends(*) 213
8.3 Homogeneous and universal graphs* 222
8.4 Connectivity and matching 225
8.5 Graphs with ends: the topological viewpoint 235
8.6 Recursive structures 248
Exercises 251
Notes 261
9. Ramsey Theory for Graphs 269
9.1 Ramsey’s original theorems* 270
9.2 Ramsey numbers(*) 273
9.3 Induced Ramsey theorems 276
9.4 Ramsey properties and connectivity(*) 286
Exercises 289
Notes 290
10. Hamilton Cycles 293
10.1 Sufficient conditions* 293
10.2 Hamilton cycles and degree sequences* 297
10.3 Hamilton cycles in the square of a graph 300
Exercises 305
Notes 306
11. Random Graphs 309
11.1 The notion of a random graph* 310
11.2 The probabilistic method* 315
11.3 Properties of almost all graphs* 318
11.4 Threshold functions and second moments 322
Exercises 329
Notes 330
12. Minors, Trees and WQO 333
12.1 Well-quasi-ordering* 334
12.2 The graph minor theorem for trees* 335
12.3 Tree-decompositions 337
12.4 Tree-width and forbidden minors 345
12.5 The graph minor theorem(*) 359
Exercises 368
Notes 373
A. Infinite sets . 377
B. Surfaces 383
Hints for all the exercises. 391
Index 419
Symbol index 435
410 pages, Softcover
Księgarnia nie działa. Nie odpowiadamy na pytania i nie realizujemy zamówien. Do odwolania !.
