An Original Speech Around the Difficult Part of the Berge Conjecture (Solved by Chudnovsky, Robertson, Seymour and Thomas)

Abstract

The Berge conjecture was proven by Chudnovsky, Robertson, Seymour and Thomas in a paper of 146 pages long (see [1]); in this manuscript, via an original speech and simple results, we rigorously simplify the understanding of this solved conjecture. It will appear that what Chudnovsky, Robertson, Seymour and Thomas were proved in their paper of 146 pages long, was an analytic conjecture stated in a very small class of graphs. We say that a graph $B$ is berge (see [4]) if every graph $B'\in \{ B, \bar{B}\}$ does not contain an induced cycle of odd length $\geq 5$ ($\bar{B}$ is the complementary graph of $B$). A graph $G$ is perfect if every induced subgraph $G'$ of $G$ satisfies $\chi(G')=\omega(G')$, where $\chi(G')$ is the chromatic number of $G'$ and $\omega(G')$ is the clique number of $G'$. The Berge conjecture states that a graph $H$ is perfect if and only if $H$ is berge. Indeed, the difficult part of the Berge conjecture consists to show that $\chi(B)=\omega(B)$ for every berge graph $B$ (Briefly, the difficult part of the Berge conjecture will be called the Berge problem (see [4])). The Hadwiger conjecture (see [4]), 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}$)). In [4], it is presented an original investigation around the Hadwiger conjecture and the Berge problem. More precisely, in [4], via two simple Theorems, it is shown that the Hadwiger conjecture and the Berge problem are curiously resembling, so resembling that they seem identical (indeed, they can be restated in ways that resemble each other). In this paper, via only original speech and results, we rigorously simplify the understanding of the Berge problem. Moreover, it will appear that what Chudnovsky, Robertson, Seymour and Thomas were proved in their manuscript of 146 pages long, was an analytic conjecture stated in a very small class of graphs.