Minors in large and 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.