Thèse Lucas PASTOR

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.