Decomposing Berge graphs
AbstractA 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Université Panthéon-Sorbonne (Paris 1) in its series Cahiers de la Maison des Sciences Economiques with number b06002.
Length: 50 pages
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
Perfect graph; Berge graph; 2-join; even skew partition; decomposition.;
Find related papers by JEL classification:
- C69 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Other
This paper has been announced in the following NEP Reports:
- NEP-ALL-2006-03-05 (All new papers)
You can help add them by filling out this form.
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.