Research on Graph Coloring and Graph Structure

图着色与图结构研究

• 批准号: 2348702
• 负责人: Xingxing Yu
• 金额: $ 26.08万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2027-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2348702&HistoricalAwards=false
• 关键词: Research; Graph; Coloring; Structure

This research project studies the existence of certain configurations in graphs, as well as connections between those configurations and global properties of graphs. A well-known example is the Four-Color Theorem, which states that if a graph does not contain two specific configurations, then it is planar, and its vertices can be partitioned into at most four sets with no edges within each set. This project seeks similar results for other configurations, as well as sufficient conditions that guarantee the existence of certain configurations (such as cycles and matchings) in graphs. This project also contains research problems related to cycles in graphs and matchings in hypergraphs that are suitable for graduate students.This research project investigates two problems on graph coloring and graph structure. Hajos conjectured that graphs containing no subdivision of the 5-vertex complete graph are 4-colorable, which would generalize the Four-Color Theorem. Prior work on this conjecture led to the substantial understanding of the structure of those graphs, as well as its connections to several important problems concerning graph structures, including Lovasz's conjecture on non-separating paths and Thomassen's conjecture on 3-linked graphs. Another problem involves bounding the chromatic number of graphs not containing a given tree as an induced subgraph. Special trees will be considered to gain insight into this problem.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该研究项目研究了图中某些配置的存在，以及这些配置与图形的全局属性之间的连接。一个众所周知的示例是四色定理，该定理指出，如果图形不包含两个特定的配置，则它是平面，并且其顶点可以在最多四组中分配到每个集合中没有边缘的四组。该项目为其他配置寻求类似的结果，以及足够的条件，以保证图形中某些配置（例如循环和匹配）的存在。该项目还包含与适合研究生的图形和匹配中的周期有关的研究问题。该研究项目研究了图形着色和图形结构的两个问题。 Hajos猜想，没有5个vertex完整图的图形是4色的，这将概括为四色定理。对此猜想的先前工作导致了对这些图的结构的实质性理解，以及与有关图形结构的几个重要问题的联系，包括Lovasz在非分离路径上的猜想以及Thomassen在3链图上的猜想。 另一个问题涉及将不包含给定树作为诱导子图的图形数量界定。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响评论标准来评估的，这将被认为是对这个问题的洞悉。