Graph and Digraph Minors

这是一笔仅用于资助研究生的补助金。调查工作的两个主要议题- Hadwiger的猜想，和扩展的图形未成年人项目。(a)Hadwiger猜想（1943年提出）指出，任何不能收缩到n-节点完全图的图都应该是n-1色的。 对于小的n，这是真的-例如，对于n = 5和n = 6，它等价于四色定理。对于所有较大的n，它是开放的。(b)由Neil Robertson和调查员完成的图未成年人项目是一项重要的工作，跨越了23篇长论文，其中使用图结构理论解决了几个悬而未决的问题。其中最困难的一步是证明所有具有大树宽的图都有大的网格子图，最近Diestel等人找到了这个重要事实的简短证明。因此，图子项目的几个简化扩展现在看来是可行的。这项工作是在图论中。图是节点的网络，其中一些节点对通过链路连接-例如电话网络或平面连接的网络。为了在图上设计快速算法，利用图的特殊性质通常是很重要的-例如，也许它可以在没有交叉的情况下绘制，或者它可以通过将非常小的图拼凑在一起构建成树结构。拥有这样一个有用的全局结构与不包含某些子结构密切相关。上面的第一个问题是，排除了任何给定子结构的图在某种意义上是否像那些可以在没有交叉的情况下绘制的图。第二部分研究了所有不含格状子结构的图都可以表示为小图的树结构的定理。

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.