For more than one hundred years, the development of graph theory was inspired andguidedmainlybytheFour-ColourConjecture.Theresolutionoftheconjecture by K. Appel and W. Haken in 1976, the year in which our ?rst bookGraph Theory with Applications appeared, marked a turning point in its history. Since then, the subject has experienced explosive growth, due in large measure to its role as an essential structure underpinning modern applied mathematics. Computer science and combinatorial optimization, in particular, draw upon and contribute to the development of the theory of graphs. Moreover, in a world where communication is of prime importance, the versatility of graphs makes them indispensable tools in the design and analysis of communication networks. Building on the foundations laid by Claude Berge, Paul Erd? os, Bill Tutte, and others, a new generation of graph-theorists has enriched and transformed the s- ject by developing powerful new techniques, many borrowed from other areas of mathematics. These have led, in particular, to the resolution of several longsta- ing conjectures, including Berge’s Strong Perfect Graph Conjecture and Kneser’s Conjecture, both on colourings, and Gallai’s Conjecture on cycle coverings.
By the authors of the classic text, Graph Theory with ApplicationsServes as both a textbook and an introduction to graph theory research, suitable for both mathematicians and computer scientistsFeatures many new exercises of varying levels of difficulty to help the reader master the techniquesAn accompanying website/blog at blogs.springer.com/bondyandmurty provides a forum for further discussion and a wealth of supplementary material