Graph and Digraph Structure

这个项目包括图论的三条研究线。(1)设计一种快速的算法来检验有向图是否具有偶长电路。这是一个众所周知的开放问题，有许多代数分支。在撰写本文时，研究者尼尔·罗伯逊和罗宾·托马斯已经取得了实质性的进展，但进一步的发展是必要的。(2)发展有向图次次理论，与非常成功的图次次理论平行；由于最近伽莱-杨格猜想的解答，这个问题现在变得可以接近了。“无方向”理论已经产生了许多广泛关注和适用的结果和算法，研究者认为“有方向”理论也取得了类似的成功。(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.