Tweaking the constant in the Linear Hadwiger Theorem

Abstract

Norin and Steiner recently proved the Linear Hadwiger Conjecture. That is, there is an absolute constant $C$ such that every graph $G$ satisfies $\chi (G)⩽C\text{had}(G)$, where $\chi (G)$ is the chromatic number and $\text{had}(G)$ is the Hadwiger number of $G$. They estimate that their proof gives a non-optimised constant $C$ of order $10^{100}$. This paper uses AI assistance to optimise their argument, and shows that every graph $G$ satisfies $\chi (G)⩽1,118,430\text{had}(G)$.

arXiv commentv1 This paper was first submitted to the arXiv shortly before the announcement of the disproof of Hadwiger's Conjecture. v2 The main constant is improved to 1,118,430