Graph and Digraph Structure

点击翻译按钮获取中文摘要

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.