Titre : A class of perfectly contractile graphs

Auteurs : Frédéric MAFFRAY & Nicolas TROTIGNON

Résumé:

Nous considérons la classe A des graphes qui ne contiennent ni trou impair, ni antitrou, ni "stretcher'" (graphe qui consiste en deux triangles disjoints avec trois chemins disjoints entre eux). Nous démontrons que tout graphe G dans A, différent d'une clique, possède une "paire d'amis" (deux sommets qui ne sont pas reliés par un chemin de longueur impaire sans corde). Notre démonstration est un algorithme qui produit en temps polynomial une paire d'amis ayant la propriété additionnelle que la contraction de ces deux sommets donne un graphe qui est aussi dans A. Ceci entraine l'existence d'un algorithme polynomial, basé sur la contraction successive de paires d'amis, pour colorer optimalement tout graphe de A. Ceci généralise plusieurs résultats concernant des familles classiques de graphes parfaits.

Abstract:

We consider the class A of graphs that contain no odd hole, no antihole, and no "stretcher" (a graph consisting of two disjoint triangles with three disjoint paths between them). We prove that every graph G in A, different from a clique has an "even pair" (two vertices that are not joined by a chordless path of odd length). Our proof is a polynomial-time algorithm that produces an even pair with the additional property that the contraction of this pair yields a graph in A. This entails a polynomial-time algorithm, based on successively contracting even pairs, to color optimally every graph in A. This generalizes several results concerning some classical families of perfect graphs