Graph Theory: An Advanced Course

Adrian Bondy, U.S.R. Murty9781846289699, 1846289696, 184628970X

Graph theory is a flourishing discipline containing a body of beautiful and powerful theorems of wide applicability. Its explosive growth in recent years is mainly due to its role as an essential structure underpinning modern applied mathematics – computer science, combinatorial optimization, and operations research in particular – but also to its increasing application in the more applied sciences. The versatility of graphs makes them indispensable tools in the design and analysis of communication networks, for instance.The primary aim of this book is to present a coherent introduction to the subject, suitable as a textbook for advanced undergraduate and beginning graduate students in mathematics and computer science. It provides a systematic treatment of the theory of graphs without sacrificing its intuitive and aesthetic appeal. Commonly used proof techniques are described and illustrated, and a wealth of exercises – of varying levels of difficulty – are provided to help the reader master the techniques and reinforce their grasp of the material.A second objective is to serve as an introduction to research in graph theory. To this end, sections on more advanced topics are included, and a number of interesting and challenging open problems are highlighted and discussed in some detail. Despite this more advanced material, the book has been organized in such a way that an introductory course on graph theory can be based on the first few sections of selected chapters.

---

Table of contents :
Preface……Page 6
Contents……Page 10
1 Graphs……Page 12
2 Subgraphs……Page 49
3 Connected Graphs……Page 88
4 Trees……Page 108
5 Nonseparable Graphs……Page 125
6 Tree-Search Algorithms……Page 142
7 Flows in Networks……Page 164
8 Complexity of Algorithms……Page 180
9 Connectivity……Page 212
10 Planar Graphs……Page 249
11 The Four-Colour Problem……Page 292
12 Stable Sets and Cliques……Page 300
13 The Probabilistic Method……Page 333
14 Vertex Colourings……Page 361
15 Colourings of Maps……Page 395
16 Matchings……Page 416
17 Edge Colourings……Page 454
18 Hamilton Cycles……Page 474
19 Coverings and Packings in Directed Graphs……Page 506
20 Electrical Networks……Page 530
21 Integer Flows and Coverings……Page 560
Unsolved Problems……Page 586
References……Page 595
General Mathematical Notation……Page 625
Graph Parameters……Page 627
Operations and Relations……Page 629
Families of Graphs……Page 631
Structures……Page 632
Other Notation……Page 634
Index……Page 637