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.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00008558 |
| Date | 28 September 2004 |
| Creators | Trotignon, Nicolas |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.001 seconds