Structure and Coloring of Sparse Graphs

点击翻译按钮获取中文摘要

The PI proposes to continue his investigation of interplay between extremal, structural and coloring properties of sparse graphs, focusing on minor-closed graph classes. Graph minor theory is a deep and rich area of graph theory, initially developed by Robertson and Seymour in a series of twenty three papers. It continues to be an active area of research with extensive algorithmic applications. Some of the methods developed as part of the theory have been successfully used in practical computations. One of the central results in graph minor theory is the graph structure theorem of Robertson and Seymour, which gives an approximate structural description of graphs that do not contain a fixed graph as a minor. The PI proposes to continue his ongoing long term project, started jointly with Robin Thomas, the goal of which is a refinement of many aspects of this theory. In particular, one of the goals of the project is to obtain bounds on connectivity which guarantees existence of certain minors and related configurations (linkages, topological minors, etc.) in graphs of given size. Luke Postle and the PI recently obtained effective bounds of the type mentioned above, which allowed them to make progress towards Hadwiger's conjecture, a longstanding question, which greatly strengthens the Four Color Theorem. This conjecture is possibly the most famous open problem in graph theory, and the PI proposes to continue sharpening the tools which allowed recent progress in search for further breakthroughs. Finally, The PI also proposes to continue investigation of extremal aspects of graph minor theory and the development of a suite of generic tools for problems in this area.