The complete short proof of the Berge conjecture

Ikorong Anouk

Abstract


We say that a graph B is berge if every graph B' ∈ {B,} does not contain an induced cycle of odd length ≥ 5 [ is the complementary graph of B}.

A graph G is perfect if every induced subgraph G' of G satisfies χ(G')=ω(G'), where χ(G') is the chromatic number of G' and ω(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 Berge problem (or the difficult part of the Berge conjecture) consists to show that χ(B)=ω(B) for every berge graph B. In this paper, we give the direct short proof of the Berge conjecture by reducing the Berge problem into a simple equation of three unknowns and by using trivial complex calculus coupled with elementary computation and a trivial reformulation of that problem via the reasoning by reduction to absurd [we recall that the Berge conjecture was first proved by Chudnovsky, Robertson, Seymour and Thomas in a paper of at least 143 pages long. That being said, the new proof given in this paper is far more easy and more short].

Our work in this paper is original and is completely different from all strong investigations made by Chudnovsky, Robertson, Seymour and Thomas in their manuscript of at least 143 pages long.


Keywords


True pal, parent, berge, the berge problem, the berge index, relative subgraph, uniform graph, bergerian, bergerian subgraph, maximal bergerian subgraph, berge caliber, tackle

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2022.6.1.1

References

I. Annouk, Around the Hadwiger conjecture and the Berge problem, Int. J. Math. Comb., 3 (2012), 72–82.

C. Berge, Graphs (Chap. 16), Third revised edition, North Holland Mathematical Library, (1991).

M. Chudnovsky, N. Roberston, P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. Math., 164(1) (2006), 51–229.


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats