×
Suggest this Article to:
TOP INDEXERS
Public Paper
-
WE LEARN ABOUT THE BERGE PROBLEM (THE ORIGINAL REFORMULATION OF THE BERGE PROBLEM AND THE ALGEBRAIC REFORMULATION OF T...
ISSN: 2195-1381
Publisher: author
WE LEARN ABOUT THE BERGE PROBLEM (THE ORIGINAL REFORMULATION OF THE BERGE PROBLEM AND THE ALGEBRAIC REFORMULATION OF T...
View Paper PDF
Abstract
We say that a graph B is berge (see [2] or [3] ) if every graph B0 ∈ {B, B¯} does not contain an induced cycle of odd length ≥ 5 [B¯ is the complementary graph of B ]. A graph G is perfect if every induced subgraph G0 of G satisfies χ(G0) = ω(G0 ), where χ(G0) is the chromatic number of G0 and ω(G0 ) is the clique number of G0. 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 original reformulation of the Berge problem and the algebraic reformulation of the Berge problem. The algebraic reformulation of the Berge problem shows that the short proof of this problem ( and therefore the short proof of the Berge conjecture) is strongly linked to a very small class of graphs called uniform graphs [ we recall that the Berge conjecture was first proved b...
SUBMIT CONCEPT ASK QUESTION
International Category Code (ICC):
ICC-0202
Evaluator Publisher Relations Manager
International Article Address (IAA):
Pending
Paper Profile:
Private
Visitors: 0
Paper Evaluation: Pending
ASI-Factor: 0
Paper Improving: Pending
Paper Flaws: 0
References
[1]. Chudnovsky, Roberston, Seymour and Thomas.The strong perfectgraph theorem. Annals of Mathematics (2004)
[2]. C. Berge.Graphs (Chap.16). Third revised edition, North HollandMathematical Library(1991).
[3] Ikorong Annouk.Around The Hadwiger Conjecture And The Berge Prob-lem. International Journal Of Mathematical Combinatorics; Vol3; 2012,72−82.
