Decomposing Berge graphs

Nicolas Trotignon ()
Additional contact information
Nicolas Trotignon: Centre d'Economie de la Sorbonne

Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1)

Abstract: A hole in a graph is an induceed cycle on at least four vertices. A graph is Berge if it has no old hole and if its complement has no odd hole. In 2002, Chudnovsky, Robertson, Seymour and Thomas proved a decomposition theorem for Berge graphs saying that every Berge graph either is in a well understood basic class or has some kind of decomposition. Then, Chudnovsky proved a stronger theorem by restricting the allowed decompositions and another theorem where some decompositions were restricted while other decompositions were extended. We prove here a theorem stronger than all those previously known results. Our proof uses at an essential step one of the theorems of Chudnovsky

Keywords: Perfect graph; Berge graph; 2-join; even skew partition; decomposition (search for similar items in EconPapers)
JEL-codes: C69 (search for similar items in EconPapers)
Pages: 50 pages
Date: 2006-01
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://halshs.archives-ouvertes.fr/halshs-00082823 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:mse:wpsorb:b06002

Access Statistics for this paper

More papers in Cahiers de la Maison des Sciences Economiques from Université Panthéon-Sorbonne (Paris 1) Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().