Return to search

Graphes parfaits : structure et algorithmes

Ce travail a pour motivation une meilleure compréhension des graphes parfaits. La preuve en 2002 de la conjecture des graphes parfaits de Claude Berge par Chudnovsky, Robertson, Seymour et Thomas a jeté une lumière nouvelle sur ce domaine de la combinatoire, mais a laissé plusieurs questions en suspens, notamment l'existence d'un algorithme combinatoire de coloration des graphes parfaits. Une paire d'amis d'un graphe est une paire de sommets telle que tous les chemins les reliant sont de longueur paire. Comme l'ont montré Fonlupt et Urhy, la contraction d'une paire amis préserve le nombre chromatique du graphe, et appliquée récursivement, permet dans certains cas de colorier optimalement le graphe. Nous prouvons une conjecture de Everett et Reed affirmant que cette approche fonctionne pour une classe de graphes parfaits: les graphes d'Artémis. Nous en déduisons un algorithme de coloration des graphes Artémis de complexité O(mn^2). Nous donnons un algorithme de complexité O(n^9) pour la reconnaissance des graphes d'Artémis. D'autres algorithmes de reconnaissance sont donnés, tous fondés sur des routines de détection de sous-graphes dans des graphes de Berge. Nous montrons que ces problèmes de détection sont NP-complets si on cherche à les étendre aux graphes quelconques.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00008558
Date28 September 2004
CreatorsTrotignon, Nicolas
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0017 seconds