Regarding the Hadwiger Conjecture

Abstract

The Hadwiger conjecture (see [1] or [2]) is well known. The Hadwiger conjecture states that every graph G satisfies χ(G) ≤ η(G) [where η(G) is the hadwiger number of G (i.e. the maximum of p such that G is contractible to the complete graph K_p), and χ(G) is the chromatic number of G. We recall (see [2]) that the famous four-color problem is a special case of the Hadwiger conjecture]. In this paper, we give the original reformulation of the Hadwiger conjecture and the algebraic reformulation of the Hadwiger conjecture. The algebraic reformulation of the Hadwiger conjecture (which is based on the original reformulation of the Hadwiger conjecture) shows that the proof of this conjecture is strongly linked to a very small class of graphs.