Hadwiger number always upper bounds the chromatic number -- 1852-1943 -- A far-reaching generalisation of Guthrie's postulate

Abstract

In a simple graph $G$, we prove that the \textit{Hadwiger number}, $h(G)$, of the given graph $G$ always upper bounds the \textit{chromatic number}, $\chi (G)$, of the given graph $G$, that is, $\chi (G)\le h(G)$. This simply stated problem is one of the fundamental questions in combinatorial mathematics, which was made by Hugo Hadwiger in 1943. Consequently, it independently verifies the most famous Four-Color Theorem: the case $h(G)=4$ is equivalent to the Four-Color Theorem, that is, every planar graph is $4$-colourable. In our novel approach, we use algebraic settings over a finite field ${\mathbb{Z}}_p$. The algebraic setting, in essence, begins with the complete graph with $h(G)$ vertices (which is a minor, $\mathcal{M}$, of the given graph $G$) and iteratively extends to the simple graph $G$. This conjecture has remained elusive, owing to a lack of understanding of the interdependence, particularly the importance of Lemma 3.1, Lemma 3.2, Lemma 3.3, and Lemma 3.6 in Section 3.

arXiv commentApart from the typo corrections, there have been no major changes in this fifth-version. %Apart from the addition of, Figure 2-11, Remark 3.6, typo corrections, and minor explanation refinements as and where necessary, there have been no major changes in this fourth-version.% %Apart from the addition of Lemma 3.5, there are no major changes in version-3.%