Graph and Digraph Minors

这是一项资助研究生的助学金。研究人员主要研究两个主题-Hadwiger猜想和图子集项目的扩展。(A)Hadwiger猜想(1943年提出)指出任何图不能收缩到n节点完全图都应该是n-1色的。对于小的n，它是真的--例如，当n=5和n=6时，它等价于四色定理。对于所有较大的n，它是开放的。(B)由Neil Robertson和调查者所做的Graph Minor项目是一项主要工作，跨越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.