Decomposing Berge graphs

Nicolas Trotignon (1)

1 CES - Centre d'économie de la Sorbonne

A hole in a graph is an induced 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.

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. Chudnovsky a aussi prouvé un autre théorème où certaines décompositions sont restreintes tandis que d'autres sont étendues. Nous prouvons ici un théorème plus fort que ces trois résultats, en ce sens qu'il les implique facilement. Notre preuve utilise l'un des théorèmes de Chudnovsky.

Mots clés: even skew partition; 2-join; Berge graph; Perfect graph; decomposition

Domaines: Economies et finances

Nicolas Trotignon. Decomposing Berge graphs. 2006. ⟨halshs-00082823⟩