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.
