A new decomposition theorem for Berge graphs

Nicolas Trotignon ()
Additional contact information
Nicolas Trotignon: CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: 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.

Keywords: 2-join; decomposition; Berge; Graph; skew partition (search for similar items in EconPapers)
Date: 2005-11
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00196448v1
References: View complete reference list from CitEc
Citations:

Published in 2005

Downloads: (external link)
https://shs.hal.science/halshs-00196448v1/document (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:hal:journl:halshs-00196448

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().