Graph and Digraph Minors

图和有向图未成年人

• 批准号: 0070912
• 负责人: Paul Seymour
• 金额: $ 13.24万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-06-15 至 2004-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0070912&HistoricalAwards=false
• 关键词: Graph; 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.

这是一笔只给研究生的助学金。研究者主要研究两个主题——哈维格猜想和图的扩展。(a)哈维格猜想（1943年提出）指出，任何不能与n节点完全图收缩的图都可以用n-1种颜色着色。对于小n，它是正确的-例如，对于n = 5和n = 6，它等价于四色定理。对于所有大于n的，它是开放的。(b) Neil Robertson和研究者的未成年图项目（graph minor project）是一项重要的工作，包括23篇长篇论文，利用图结构理论解决了几个悬而未决的问题。其中最困难的步骤之一是证明所有树宽较大的图都有较大的网格子图，最近Diestel等人找到了一个简短而简单的证据来证明这个重要事实。因此，图小项目的几个推测扩展现在看来是可行的。这是图论方面的工作。图是一个节点网络，其中一些节点对通过链接连接起来，例如电话网或平面连接网络。为了在图上设计快速算法，利用图的特殊属性通常是很重要的——例如，也许它可以在没有交叉的情况下绘制，或者也许它可以通过将非常小的图拼接在一起以树状结构构建。拥有这样一个有用的全局结构与不包含某些子结构密切相关。上面的第一个问题是，排除任何给定子结构的图在某种意义上是否与不需要交叉的图相似。第二章研究了所有不包含类网格子结构的图都可以表示为小图的树状结构的定理。