A new decomposition theorem for Berge graphs

Nicolas Trotignon (1)

1 CERMSEM - CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique

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.

Un trou dans un graphe est un cycle induit avec au moins quatre sommets. Un graphe est de Berge si ni lui ni son complémentaire ne contiennent de trou impair. En 2002, Chudnovsky, Robertson, Seymour et Thomas ont prouvé un théorème de décomposition affirmant que tout graphe de Berge, ou bien appartient à une classe basique bien comprise, ou bien admet un certain type de décomposition. Puis Chudnovsky a prouvé un théorème plus fort en restreignant les décompositions autorisées. Nous prouvons ici un théorème plus fort, en restreignant encore les décompositions autorisées. Nos motivations seront données dans un travail ultérieur actuellement en préparation.

Mots clés: 2-join; decomposition; Berge; Graph; skew partition

Domaines: Economies et finances

Nicolas Trotignon. A new decomposition theorem for Berge graphs. 2005. ⟨halshs-00196448⟩