Complete minors in graphs with only a few colourings

点击翻译按钮获取中文摘要

Hadwigers Conjecture from 1943 states that for every natural number k every graph either admits a colouring of the vertices with k colours such that adjacent vertices receive distinct colours, or contains k+1 many disjoint, connected, pairwise adjacent subgraphs (a so-called complete minor of order k+1). The problem is one of the most important open questions in graph theory. We consider the case that the graph under consideration admits only a restricted number of colourings with k colours.