A new decomposition theorem for Berge graphs
A hole in a graph is an induced cycle on at least four vertices. A graph is Berge if it has no odd 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. We prove here a stronger theorem by restricting again the allowed decompositions. Motivation for this new theorem will be given in a work in preparation.
|Date of creation:||Nov 2005|
|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:b05079. 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.