دانلود کتاب گراف‌های فرعی

The theory of graph minors has a rich history starting with Kuratowski’s character-ization of planar graphs, intertwines with the graph coloring through Hadwiger’s conjecture, and plays an important role in algorithmic graph theory. The devel-opment of the structural characterization of graphs avoiding a fixed minor by Robertson and Seymour is arguably the most important foundational result in structural graph theory. And, if any of this is news to you, this book is probably not for you. There are quite a few books that present the basic concepts of the theory. They will explain to you the importance of forbidden minors in relation to graphs on surfaces and other proper minor-closed classes, the notion of treewidth and its applications in design of efficient algorithms, and Hadwiger’s conjecture and its relationship to the Four Color Theorem. They will speak about well-quasi-ordering, Wagner’s conjecture, and the amazing fact that every minor-monotone property is characterized by only finitely many forbidden minors. They will maybe state the Minor Structure Theorem with all its technical and slightly mysterious ingredients, and if you are lucky, actually explain to you why the ingredients are needed and how the theorem can be used. And they will let you hanging there, aware that there is a lot to the theory that you do not see. Admittedly, this is already enough for you to appreciate many of the applications of the theory, or even to use it in your research. But if you want to learn more, there are not that many options available. You can go hardcore and actually read the series of papers by Robertson and Seymour, or some of the newer developments of the theory. This is indeed possible, but of course journal papers need to show all the details of every argument, no matter how distracting from the important ideas. Adding to the difficulty, it needs to be admitted that many of the papers on graph minors theory are not written in an especially reader-friendly way. And, in the end, you may end up knowing a lot of theory without actually being able to use it. So perhaps you could go the other way, start by studying various applications of the theory, gain an understanding of what is important in this way, and gradually learn the details as needed. This seems to be the most popular avenue, usually with the help of a mentor who can point you to the right materials on each particular aspect. Unsurprisingly, this top-down approach leaves you with a great overall understanding, but somewhat shaky foundations. Or, you could give this book a try. As far as I am aware, this is the first book to offer a somewhat comprehensive treatment of the intermediate and advanced aspects of the theory of graph minors. The book is split into three parts: • Part I discusses in detail the ideas and notions that are used in the proof of the Minor Structure Theorem and its applications. It starts with the development of the theory of tree decompositions and dual objects such as tangles and brambles. A significant attention is given to graphs drawn on surfaces, especially in connection the metric arising from tangles that respect the drawings and the corresponding sufficient conditions for the presence of minors. Building on these results, we prove the Flat Wall Theorem and explain how it is used in the algorithm to test whether the input graph contains a fixed minor. Finally, we give a detailed outline of the proof of the Minor Structure Theorem. • Part II showcases applications of the Minor Structure Theorem of various com-plexity. We take this as an opportunity to introduce several important properties of graphs from proper minor-closed classes (existence of low-treewidth colorings and large grid minors), and to talk about recent progress on the structural theory of topological minors. This part also introduces and motivates several strengthenings of the Theorem that simplify handling of apices and vortices, the main technical ingredients. • Part III is devoted to results on graph minors that avoid the Structure Theorem, on topics such as sublinear separators, density, isomorphism testing, …