Auteur : Lucas PASTOR Directeur de Thèse : Frédéric MAFFRAY Co directeur : Sylvain GRAVIER Date : 23 novembre 2017
Coloration, ensemble indépendant et structure de graphe
Cette thèse s'intéresse à des problèmes de coloration, d'ensemble indépendant et à la théorie structurelle des graphes.
Dans un premier temps, nous fournissons un algorithme s’exécutant en temps polynomial pour le problème de la 4-coloration dans des sous-classes de graphe sans P6. Ces algorithmes se basent sur une compréhension précise de la structure de ces classes de graphes, pour laquelle nous donnons une description complète.
Deuxièmement, nous étudions une conjecture portant sur la coloration par liste et prouvons que pour tout graphe parfait sans griffe dont la taille de la plus grande clique est bornée par 4, le nombre chromatique est égal au nombre chromatique par liste. Ce résultat est obtenu en utilisant un théorème de décomposition des graphes parfaits sans griffe, une description structurelle des graphes de base de cette décomposition et le célèbre théorème de Galvin.
Ensuite, en utilisant la description structurelle élaborée dans la première partie et en renforçant certains aspects de celle-ci, nous fournissons un algorithme s’exécutant en temps polynomial pour le problème d’indépendant de poids maximum dans des sous-classes de graphe sans P6 et sans P7.
Enfin, nous infirmons une conjecture datant de 1999 de De Simone et Körner sur les graphes normaux. Notre preuve est probabiliste et est obtenue en utilisant les graphes aléatoires.