Structure and Coloring of Sparse Graphs

稀疏图的结构和着色

• 批准号: RGPIN-2022-03246
• 负责人: Norin, Sergey
• 金额: $ 2.26万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759082
• 关键词: Structure; Coloring; 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.

PI 建议继续研究稀疏图的极值、结构和着色属性之间的相互作用，重点关注小闭图类。图次要理论是图论的一个深刻而丰富的领域，最初由 Robertson 和 Seymour 在一系列二十三篇论文中发展起来。它仍然是一个活跃的研究领域，具有广泛的算法应用。作为理论一部分开发的一些方法已成功应用于实际计算。图次要理论的核心成果之一是 Robertson 和 Seymour 的图结构定理，它给出了不包含固定图作为次要的图的近似结构描述。 PI 建议继续与 Robin Thomas 共同启动的长期项目，其目标是完善该理论的许多方面。特别是，该项目的目标之一是获得连通性的界限，以保证给定大小的图中存在某些次要项和相关配置（链接、拓扑次要项等）。 Luke Postle 和 PI 最近获得了上述类型的有效界限，这使他们能够在哈维格猜想这个长期存在的问题上取得进展，这极大地加强了四色定理。这个猜想可能是图论中最著名的开放问题，PI 建议继续改进工具，使最近在寻求进一步突破方面取得进展。最后，PI 还建议继续研究图次要理论的极值方面，并针对该领域的问题开发一套通用工具。