Graph and Digraph Structure

西摩9701598这个项目包含了图论的三个研究方向。(1)设计一种快速算法来检验有向图是否有偶数长的回路。这是一个众所周知的公开问题，有许多代数分支。在撰写本文时，研究人员尼尔·罗伯逊和罗宾·托马斯已经在这方面取得了实质性进展，但还需要进一步发展。(2)发展有向图未成年人理论，与非常成功的图未成年人理论平行；由于最近Gallai-Young猜想的解，这一理论现在变得可接近了。“无向”理论导致了许多引起广泛兴趣和适用的结果和算法，调查人员认为，“有向”理论也取得了类似的成功。(3)完成Tutte猜想推广四色定理的求解工作。包括PI在内的一组研究人员发现了四色定理本身的一个新证明，并将Tutte的猜想简化为一种可能通过修改这个新证明来证明的形式。这项研究属于组合学的一般领域。组合学的目标之一是找到有效的方法来研究离散的对象集合如何排列。离散系统的行为对于现代通信来说是极其重要的。例如，大型网络的设计，如那些发生在电话系统中的网络，以及计算机科学中的算法设计，都涉及离散的对象集，这利用了组合研究。

Seymour 9701598 This project encompasses three lines of research in graph theory. (1) To design a fast algorithm to test if a directed graph has a circuit of even length. this is a well-known open problem, with a number of algebraic ramifications. At the time of this writing, the investigator, Neil Robertson and Robin Thomas have made substantial progress with it, but further development is necessary. (2) To develop a theory of digraph minors, parallel to the highly successful theory of graph minors; this is made approachable now because of the recent solution of the Galllai-Younger conjecture. The ``undirected'' theory has led to numerous results and algorithms of wide interest and applicability, and the investigator believes that similar success with the ``directed'' theory. (3) To complete work on solving Tutte's conjectured extension of the four-colour theorem. A group of researchers, including the PI, has found a new proof of the four-colour theorem itself, and they have reduced Tutte's conjecture to a form which can probably be proved by modifying this new proof. 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.