Decomposing Berge graphs
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.
|Date of creation:||Jan 2006|
|Date of revision:|
|Contact details of provider:|| Postal: 106 - 112 boulevard de l'Hôpital, 75647 Paris cedex 13|
Phone: 01 44 07 81 00
Fax: 01 44 07 81 09
Web page: http://mse.univ-paris1.fr/
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:mse:wpsorb:b06002. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Lucie Label)
If references are entirely missing, you can add them using this form.