Topological Minors of Graphs

丁9700623 该奖项提供资金的调查涉及拓扑未成年人的三个基本问题。第一个问题是Robertson的双路猜想，它指出，如果一类图G在拓扑子式下是封闭的，并且没有任意长的双路，则G不包含关于拓扑子式关系的无限反链。这是图论中的一个基本猜想。它涉及结构图理论，组合优化和经典组合学。PI已经在解决这个猜想方面取得了重大进展，其中包括但不限于证明所有小闭图类和割宽至多为3的图类的猜想。他希望他过去在这个问题上的经验，加上他的一些新的想法，将有助于他解决这个猜想完全。第二个问题是Hajos猜想的边缘版本。最近，PI通过识别所有色指数大于n的次极小图，建立了Hadwiger猜想的边版本。现在他提出研究色指数大于n的拓扑-次-极小图。这正是Hajos猜想的边缘版本，Hajos猜想认为K_n是唯一一个色数大于n的拓扑子极小图。这个问题不仅涉及Hajos猜想和Hadwiger猜想，而且还涉及Vizing的平面图猜想和这一领域的一些著名结果。第三个问题是关于大交叉数的不可避免图。 交叉数是一个典型的图参数，它对拓扑-子式关系是单调的，但对子式关系不是单调的。关于这个参数的一个自然问题是理解是什么使交叉数大。一个明显的原因是图的高亏格。还有其他原因。例如，对于某个大的n，拓扑子式D_ n的包含可以使交叉数变大。PI提出了一个刻画不可避免的大交叉数图的完整列表的方法。 这项研究是在组合数学的一般领域。组合数学的目标之一是找到有效的方法来研究如何安排对象的离散集合。离散系统的行为对现代通信极为重要。例如，大型网络的设计，如电话系统中的网络设计，以及计算机科学中的算法设计，都要处理离散的对象集，这就需要使用组合研究。

Ding 9700623 This award provides funds for an investigation of three fundamental problems involving topological minors. The first problem is Robertson's double-path conjecture, which states that if a class G of graphs is closed under topological minors and is free of arbitrarily long double-paths, then G does not contain infinite antichains with respect t o the topological-minor relation. This is a fundamental conjecture in graph theory. It relates structural graph theory, combinatorial optimization, and classical combinatorics. The PI has made significant progress towards solving this conjecture, which includes, but is not limited to, proving the conjecture for all minor-closed classes of graphs and for the class of graphs of cutwidth at most three. He hopes that his past experience on this problem together with some of his new ideas will help him to settle this conjecture completely. The second problem is the edge version of Hajos' conjecture. Recently, the PI has established the edge version of Hadwiger's conjecture by identifying all minor- minimal graphs with chromatic index greater than n. Now he proposes to study topological-minor-minimal graphs with chromatic index greater than n. This is exactly the edge version of Hajos' conjecture, which claims that K_n is the only topological-minor-minimal graph with chromatic number greater than n. This problem relates not only to Hajos' conjecture and Hadwiger's conjecture, but also to Vizing's planar graph conjecture and several well-known results in this field. The third problem concerns unavoidable graphs of large crossing number. Crossing number is a typical graph parameter that is monotone with respect to the topological-minor relation but not with respect to the minor relation. A natural problem concerning this parameter is to understand what makes the crossing number big. One obvious cause is a high genus for the graph. There are also other causes. For example, for some large n, the containment of a topological minor D_ n can make the crossing number large. The PI proposes to characterize the complete list of unavoidable graphs of large crossing number. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.