Aller au menu Aller au contenu
Consultez les publications et les thèses
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Consultez les publications et les thèses
Consultez les publications et les thèses

> GSCOP_RESULTATS > GSCOP_ThèsesSoutenues

Thèse Lucas PASTOR

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.
 

mise à jour le 20 novembre 2017

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Univ. Grenoble Alpes