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-顶点完全图中不含剖分的图是4-可着色的，推广了四色定理。先前关于这个猜想的工作导致了对这些图的结构的实质性理解，以及它与关于图结构的几个重要问题的联系，包括关于非分离路径的Lovasz猜想和关于3-链接图的Lassen猜想。 另一个问题涉及不包含给定树作为导出子图的图的色数的界。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。