Soutenance de thèse de Lucas Pastor le 23 novembre 2017 à 14 H en amphi C - Site Viallet Grenoble INP
Intitulée : Coloration, ensemble indépendant et structure de graphe - Title : Coloring, independent set and structural graph theory
Les membres du jury :
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.
Abstract :
This thesis deals with graph coloring, list coloring, maximum weight stable set and structural graph theory.
First, we provide polynomial-time algorithms for the 4-coloring problem in subclasses of P6-free graphs. These algorithms rely on a precise understanding
of the structure of these classes of graphs for which we give a full description.
Secondly, we study the list coloring conjecture and prove that for any claw-free perfect graph with clique number bounded by 4, the chromatic number
and the choice number are equal. This result is obtained by using a decomposition theorem for claw-free perfect graphs, a structural description
of the basic graphs of this decomposition and by using Galvin’s famous theorem.
Next by using the structural description given in the first part and strengthening other aspects of this structure, we provide polynomial-time
algorithms for the maximum-weight independent set problem in subclasses of P6-free and P7-free graphs.
Finally, we disprove a conjecture of De Simone and Körner made in 1999 related to normal graphs. Our proof is probabilistic and is obtained by the use of
random graphs.
- Monsieur Frédéric Havet, Directeur de recherche CNRS, INRIA, Sophia-Antipolis, Rapporteur.
- Monsieur Dieter Rautenbach, Professeur des Universités, Universität Ulm, Rapporteur.
- Monsieur Laurent Beaudou, Maître de conférences, LIMOS, Université Blaise Pascal, Examinateur.
- Monsieur Mickael Montassier, Professeur des Universités, LIRMM, Université de Montpellier, Examinateur.
- Madame Aline Parreau, Chargé de recherche CNRS, LIRIS, Université Claude Bernard Lyon 1, Examinatrice.
- Monsieur Nicolas Trotignon, Directeur de recherche CNRS, LIP, ENS Lyon, Examinateur.
- Monsieur Frédéric Maffray, Directeur de recherche CNRS, G-SCOP, Université Grenoble-Alpes, Directeur de thèse.
- Monsieur Sylvain Gravier, Directeur de recherche CNRS, Institut Fourier, Université Grenoble-Alpes, Co-directeur de thèse.
Résumé:
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.
Abstract :
This thesis deals with graph coloring, list coloring, maximum weight stable set and structural graph theory.
First, we provide polynomial-time algorithms for the 4-coloring problem in subclasses of P6-free graphs. These algorithms rely on a precise understanding
of the structure of these classes of graphs for which we give a full description.
Secondly, we study the list coloring conjecture and prove that for any claw-free perfect graph with clique number bounded by 4, the chromatic number
and the choice number are equal. This result is obtained by using a decomposition theorem for claw-free perfect graphs, a structural description
of the basic graphs of this decomposition and by using Galvin’s famous theorem.
Next by using the structural description given in the first part and strengthening other aspects of this structure, we provide polynomial-time
algorithms for the maximum-weight independent set problem in subclasses of P6-free and P7-free graphs.
Finally, we disprove a conjecture of De Simone and Körner made in 1999 related to normal graphs. Our proof is probabilistic and is obtained by the use of
random graphs.