Graph theory

More about the book

Almost two decades have passed since the foundational texts in graph theory shaped introductory courses. These texts established key fields of study and will continue to influence the discipline's development. However, significant advancements have occurred in this time, including new theorems, interrelated methods, and the emergence of new branches. Notable developments include the concept of list colouring, which connects invariants like average degree and chromatic number; the influence of probabilistic methods and the regularity lemma in extremal graph theory and Ramsey theory; and the rise of graph minors and tree decompositions, which apply surface topology to longstanding algorithmic problems. Given these changes, a reassessment of the essential areas, methods, and results for an introductory graph theory course is necessary to prepare students for future developments. This book aims to provide material for such a course, focusing on the theoretical aspects of graph theory as part of pure mathematics. It intentionally departs from the tradition of covering both theory and applications, omitting explicit algorithms and real-world applications to concentrate on the core theoretical foundations.