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还建议继续研究图子理论的极值方面，并为这一领域的问题开发一套通用工具。