### 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.#### Keywords

True pal; Parent; Berge; The Berge problem; The Berge index; Relative subgraph; Uniform graph; Bergerian; Bergerian subgraph; Maximal Bergerian subgraph

#### Full Text:

PDFDOI: http://dx.doi.org/10.26713%2Fcma.v1i3.126

### Refbacks

- There are currently no refbacks.

eISSN 0975-8607; pISSN 0976-5905