权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Disjoint Paths in Graphs and Coloring

图形和着色中的不相交路径

基本信息

批准号：
1954134
负责人：
Xingxing Yu
金额：
$ 16万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2023-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1954134&HistoricalAwards=false
关键词：
Disjoint Paths Graphs Coloring

项目摘要

Many real word problems concern large systems that may be modeled by graphs. Those systems include communication networks, social networks, and neural networks. To analyze those systems, it is important to understand the structure of the underlying graphs, in terms of the existence of certain structure, connectivity, and partitions. It is often the case that methods for studying graph structures lead to efficient algorithms. This project studies structure of graphs with certain forbidden substructures, as well as related problems on connectivity and coloring. This project also contains research problems that are suitable for students. Determining the chromatic number of an arbitrary graph is difficult. However, one might be able to obtain a reasonable bound on the chromatic numbers of graphs not containing a given structure, such as subdivisions of a graph. The PI will work on an old conjecture of Hajos: Graphs without K_5-subdivisions are 4-colorable. If true, this would be a generalization of the well known Four Color Theorem. The PI will study the structure of such graphs, as well as its connections to connectivity problems about disjoint paths in graphs, including a long standing conjecture of Lovasz on removable paths.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.

许多现实世界中的问题都与可以用图形建模的大系统有关。这些系统包括通信网络、社交网络和神经网络。要分析这些系统，重要的是要了解底层图形的结构，即某些结构、连通性和分区的存在。研究图结构的方法通常会导致高效的算法。本项目研究具有某些禁止子结构的图的结构，以及有关连通性和着色的问题。这个项目还包含了适合学生的研究问题。确定任意图的色数是很困难的。然而，人们可能能够得到不包含给定结构的图的色数的一个合理的界，例如图的细分。PI将研究Hajos的一个古老的猜想：没有K_5-细分的图是4-可染的。如果是真的，这将是著名的四色定理的推广。PI将研究这种图的结构，以及它与图中不相交路径的连通性问题的联系，包括Lovasz关于可移除路径的长期猜想。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。