Minors in large and highly connected graphs

大型且高度关联的图表中的未成年人

• 批准号: 157434833
• 负责人: Professor Dr. Reinhard Diestel
• 金额: --
• 依托单位: Fachbereich Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2009
• 资助国家: 德国
• 起止时间: 2008-12-31 至 2013-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/157434833?language=en
• 关键词: Minors; large; highly; connected; graphs

It is a fundamental concern of graph theory to understand the interaction of graph invariants and their ability to force local substructures. We want to investigate how the invariants chromatic number, average degree, and connectivity are able to force minors, in particular dense minors, and how they differ from each other in this respect. In spite of the diversity of these invariants, few qualitative differences are known concerning their power to force dense minors. However, Hadwiger’s conjecture, one of the central open questions in graph theory, implies that there is such a difference. It has recently been noticed that the structural characterizations of Kr-minorfree graphs due to Robertson and Seymour appear to imply that, for large graphs, high connectivity forces denser minors than high average degree does. These investigations combine methods of graph minor theory and connectivity theory in a new and unprecedented way. In a group consisting of representatives of both these fields we would like to look further into these developments and thus help to shed some more light on the area of Hadwiger’s conjecture.

理解图不变量之间的相互作用及其强制局部子结构的能力是图论的一个基本问题。我们想研究不变量色数、平均度和连通性如何能够强制子式，特别是稠密子式，以及它们在这方面的不同之处。尽管这些不变量的多样性，很少有质的差异是已知的关于他们的力量，迫使密集的未成年人。然而，Hadwiger猜想，图论中的中心开放问题之一，暗示存在这样的差异。最近人们注意到，由于Robertson和Seymour的Kr-minorfree图的结构特征似乎意味着，对于大型图，高连通度比高平均度迫使更密集的子图。这些调查结合联合收割机的方法图子理论和连通性理论在一个新的和前所未有的方式。在一个由这两个领域的代表组成的小组中，我们想进一步研究这些发展，从而有助于阐明哈德维格猜想的一些方面。