Graph Minors

Graph minor theory is one of the most influential and well-developed areas of graph theory, yet its key results, particularly the work of Robertson and Seymour, have remained scattered across numerous technical papers. This book fills an important gap by providing a comprehensive, structured treatment of the subject.

Divided into three main parts, the book first introduces the fundamentals of graph minor theory, focusing on the deep and powerful Minor Structure Theorem. It offers a clear roadmap for understanding the theorem's proof, presenting its key ingredients while omitting only the most technical details. The second part explores a variety of applications, from algorithmic results to connections with the Linear Hadwiger Conjecture and graph coloring problems. The final section presents alternative approaches to graph minor theory that do not rely on the Minor Structure Theorem, covering topics such as sublinear separators, density, and isomorphism testing.

The exposition is rigorous yet accessible, striving to balance depth with readability. While some parts remain dense due to the complexity of the subject, the author provides valuable insights and explanations that make challenging concepts more approachable. The book not only serves as an excellent learning resource for graduate students and researchers entering the field but also as a long-lasting reference for experts.

Offers a comprehensive treatment of both intermediate and advanced aspects of the theory of graph minors Consolidates material from numerous technical papers into one comprehensive, authoritative reference Essential for researchers in the field and will remain a main reference for years to come

Autorentext

Zden k Dvöák is currently employed as a professor at Computer Science Institute of Charles University, Prague. He obtained his Master Degree (Mgr) (summa cum laude) in Computer Science at Faculty of Mathematics and Physics of Charles University, Prague in September 2004 and his PhD degree at Faculty of Mathematics and Physics of Charles University, Prague in May 2007. He is the author of over 100 papers published in journals or presented at selective conferences, with 529 citations (H-index 13 according to the Web of Science). His research interests include graph coloring, structural graph theory, and algorithms and complexity. He has been the Managing editor of the Journal of Combinatorial Theory, Series B since 2016, one of Editors-in-chief of Electronic Journal of Combinatorics since 2017 (associate editor in 2014–2016) and was the Associate editor of Discrete Mathematics (2013–2015). He is the recipient of many prestigious awards including the European Prize in Combinatorics in 2015, the prize of the Czech Union of Mathematicians for young mathematicians in 2014, the Neuron prize for young mathematicians given by Karel Janecek foundation in 2011, and the Josef Hlavka award in 2004. His hobbies include hiking, practicing Shinto Muso Ryu Jodo, reading sci-fi and fantasy books.

Inhalt

Chapter 1. Introduction.- Part I. Understanding the structure theorem.- Chapter 2. Tree decompositions and treewidth.- Chapter 3. Linkedness.- Chapter 4. Graphs on surfaces.- Chapter 5. Towards the structure theorem.- Chapter 6. Pointers and sources.- Part II. Using the structure theorem.- Chapter 7. Low-treewidth colorings.- Chapter 8. Tighter grid theorem.- Chapter 9. Topological minors.- Chapter 10. Minors in large connected graphs.- Chapter 11. Sources.- Part III. Avoiding the structure theorem.- Chapter 12. Sublinear separators.- Chapter 13. Chordal partitions.- Chapter 14. Chromatic number.- Chapter 15. Product structure.- Chapter 16. Iterated layerings.- Chapter 17. Isomorphism testing.- Chapter 18. Sources.