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在一系列23篇论文中发展起来的。它仍然是一个活跃的研究领域，有着广泛的算法应用。作为理论的一部分发展起来的一些方法已经成功地应用于实际计算中。图的子部理论的核心结果之一是Robertson和Seymour的图结构定理，它给出了不包含固定图作为子部的图的近似结构描述。PI提议继续他与罗宾·托马斯共同发起的正在进行的长期项目，目标是对这一理论的许多方面进行完善。特别是，该项目的目标之一是获得保证存在某些次要因素和相关配置(链接、拓扑性次要因素等)的连通性界限。在给定大小的图中。Luke Postle和PI最近得到了上述类型的有效界，这使得他们在Hadwiger猜想方面取得了进展，这是一个长期存在的问题，大大加强了四色定理。这一猜想可能是图论中最著名的公开问题，PI建议继续磨砺工具，这些工具允许最近在寻找进一步突破方面取得进展。最后，PI还建议继续研究图次要理论的极端方面，并开发一套通用工具来解决这一领域的问题。