The Analytic Reformulation of the Hadwiger Conjecture

Abstract

0. The Hadwiger conjecture [recall that the famous four-color problem is a special case of the Hadwiger conjecture] states that every graph $G$ satisfies $\chi(G) \leq \eta(G)$ [where $\chi(G)$ is the chromatic number of $G$, and $\eta(G)$ is the hadwiger number of $G$ (i.e.\ the maximum of $p$ such that $G$ is contractible to the complete graph $K_{p}$)]. In this paper, via an original speech and simple results, we rigorously simplify the understanding of the Hadwiger conjecture. It will appear that to solve the famous Hadwiger conjecture is equivalent to solve an analytic conjecture stated on a very small class of graphs.\textbf{1.} The Hadwiger conjecture (see [3] or [4] or [6] or [7] or [8] or [9] or [10]) and the Berge problem (see [2] or [4] or [5] or [6] or [8]) are well known. Recall in a graph $G=[V(G),E(G),\chi(G),\omega(G), \bar{G}]$, $V(G)$ is the set of vertices, $E(G)$ is the set of edges, $\chi(G)$ is the chromatic number, $\omega(G)$ is the clique number and $\bar{G}$ is the complementary graph of $G$. The Hadwiger conjecture [recall that the famous four-color problem is a special case of the Hadwiger conjecture] states that every graph $G$ satisfies $\chi(G) \leq \eta(G)$ [where $\eta(G)$ is the hadwiger number of $G$ (i.e.\ the maximum of $p$ such that $G$ is contractible to the complete graph $K_{p}$)]. We say that a graph $B$ is berge if every $B'\in \lbrace B, \bar{B}\rbrace$ does not contain an induced cycle of odd length $\geq 5$. A graph $G$ is perfect if every induced subgraph $G'$ of $G$ satisfies $\chi(G')=\omega(G')$. Indeed, the Berge problem (see [4] or [5] or [6]) consists to show that $\chi(B)=\omega(B)$ for every berge graph $B$ [we recall (see {\bf{[0]), that the Berge problem was solved in a paper of $146$ pages long by Chudnovsky, Robertson, Seymour and Thomas]. In [4], it is presented an original investigation around the Berge problem and the Hadwiger conjecture, and, via two simple Theorems, it is shown that the Berge problem and the Hadwiger conjecture are curiously resembling, so resembling that they seem identical [indeed, they can be restated in ways that resemble each other (see [4])]. Now, in this paper, via only original speech and results, we rigorously simplify the understanding of the Hadwiger conjecture. Moreover, it will appear that to solve the Hadwiger conjecture is equivalent to solve an analytic conjecture stated on a very small class of graphs