Complete minors in graphs with only a few colourings

• Applicant: Professor Dr. Matthias Kriesell
• Subject Area: Mathematics
• Term: from 2016 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 327533333

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.

• DFG Programme: Research Grants