PrefaceFor more than one hundred years, the development of graph theory was inspiredby the Four-Colour Conjecture. The resolution of the conjectureandguided maiby K.Appel and W.Haken in1976, the yearin which ourfirst book Graph Theorywith Applications appeared, marked a turning point in its history. Since then, thesubject hasexperienced explosive growth, due in large measure to its role as anessential structurre underpinning modern applied mathematics. Computer scienceand combinatorial optimization, in particular, draw upon and contribute to thedevelopment of the theory of graphs. Moreover, in a world where communicationis of prime importance, the versatility of graphs makes them indispensable toolsinthe design and analysis of comnicationnetworksBuilding on the foundations laid by Claude Berge, Paul Erds, Bill Tutte, andothers, a new generation of graph-theorists has enriched and transformed the subject by developing powerful new techniques, many borrowed from other areas ofmathematics. These have led, in particular, to the resolution of several longstanding conjectures, including Berge's Strong Perfct Graph Conjecture and Kneser'sConjecture, both on colourings,and Gallai's Conjecture on cycle coverings.One of the dramatic developments over the past thirty years has been thecreation of the theory of graph minors by G. N. Robertson and P. D. Seyour.Ina long series of deep papers, they have revolutionized graph theory by introducingan original and incisive way of viewing graphical structure. Developed to attacka celebrated conjecture of K.Wagner, their theory gives incresotrembeddings of graphs in surfaces.It hasled alsoto polynomial-timealgorithmsfor solving avariety of hitherto intractable problems, such as that ofinding acollection of pairwise-disjoint paths between prescribed pairs of vertices.A technique which has met with spectacular success is the probabilistic method.Introduced in the 1940s by Erdos, in association with fellow Hungarians A. Renyiand PTuran,this powerful yet versatile tolis being employed withever-increasingfrequency andsophisticationtoestablishtheexistenceornonexistenceofgraphsand other combinatorial structures, with specified properties.Preface For more than one hundred years, the development of graph theory was inspired and guided mainly by the Four-Colour Conjecture. The resolution of the conjecture by K. Appel and W. Haken in 1976, the year in which our first book Graph 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 sub￾ject by developing powerful new techniques, many borrowed from other areas of mathematics. These have led, in particular, to the resolution of several longstand￾ing conjectures, including Berge’s Strong Perfect Graph Conjecture and Kneser’s Conjecture, both on colourings, and Gallai’s Conjecture on cycle coverings. One of the dramatic developments over the past thirty years has been the creation of the theory of graph minors by G. N. Robertson and P. D. Seymour. In a long series of deep papers, they have revolutionized graph theory by introducing an original and incisive way of viewing graphical structure. Developed to attack a celebrated conjecture of K. Wagner, their theory gives increased prominence to embeddings of graphs in surfaces. It has led also to polynomial-time algorithms for solving a variety of hitherto intractable problems, such as that of finding a collection of pairwise-disjoint paths between prescribed pairs of vertices. A technique which has met with spectacular success is the probabilistic method. Introduced in the 1940s by Erd˝os, in association with fellow Hungarians A. R´enyi and P. Tur´an, this powerful yet versatile tool is being employed with ever-increasing frequency and sophistication to establish the existence or nonexistence of graphs, and other combinatorial structures, with specified properties