Graph and Digraph Minors

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

This is a grant for support for a graduate student only. The investigator works on two main topics - Hadwiger's conjecture, and extensions of the graph minors project.(a) Hadwiger's conjecture (proposed in 1943) states that any graph not contractible to the n-node complete graph should be colourable with n-1 colours. For small n it is true - eg for n = 5 and n = 6 it is equivalent to the 4-colour theorem. For all larger n it is open.(b) The graph minors project, by Neil Robertson and the investigator, was a major piece of work, spanning 23 long papers, which used graph structure theory to settle several open questions. One of the most difficult steps of this was proving that all graphs with large tree-width have large grid minors, and recently Diestel et al have found a short, simple proof of this vital fact. As a consequence, several conjectured extensions of the graph minors project now appear feasible.This work is in graph theory. A graph is a network of nodes, some pairs of which are joined by links - such as, for instance, a telephone network, or a network of plane connections. To design fast algorithms on graphs it is often important to make use of special properties of the graph - for instance, perhaps it can be drawn without crossings, or perhaps it can be built from very small graphs by piecing them together in a tree-structure. Having such a useful, global structure is closely related with with NOT containing certain substructures. The first problem above asks whether the graphs with ANY given substructure excluded are in some sense like those that can be drawn without crossings. The second studies the theorem that all graphs not containing a grid-like substructure can be expressed as a tree-structure of small graphs.