Disjoint Paths in Graphs and Coloring

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

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.