Quelques sujets sur la coloration des graphes orientés
19/01/2026 à 14h00
M. Gil PUIG I SURROCA présente ses travaux en soutenance le 19/01/2026 à 14h00
À l'adresse suivante : Université Paris Dauphine - PSL, Place du Maréchal-de-Lattre-de-Tassigny, 75116 Paris, France Salle des thèses - D 520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Quelques sujets sur la coloration des graphes orientés
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d'Analyse et de Modélisation de Systèmes d'Aide à la Décision
Section CNU
9 - Sciences et technologies de l'information et de la communication
Directeur(s)
Denis CORNAZ
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Denis CORNAZ | Maître de conférences | Université Paris Dauphine - PSL | Directeur de these |
| M. Louis ESPERET | Directeur de recherche | Université Grenoble Alpes | Rapporteur |
| M. Alexander SCOTT | Professor | University of Oxford | Rapporteur |
| Mme Marthe BONAMY | Directeur de recherche | Université de Bordeaux | Examinateur |
| M. Matěj STEHLíK | Professeur | Université Paris Cité | Examinateur |
| M. Ararat HARUTYUNYAN | Maître de conférences | Université Paris Dauphine - PSL | Co-encadrant de these |
| M. Kolja KNAUER | Professor | Universitat de Barcelona | CoDirecteur de these |
Résumé
On étudie le problème de partitionnement de digraphes en sous-graphes acycliques, et son paramètre associé : le nombre dichromatique. Ce paradigme, conçu par Neumann-Lara vers la fin des années 1970, nous a prodigué un bon nombre de généralisations de théorèmes classiques sur la coloration de graphes.
Nous dédions une attention spéciale aux bornes que l'on peut donner pour plusieurs classes de digraphes, comprenant les tournois locaux, les orientations des graphes de Kneser, les orientations des triangulations 2-planaires extérieures imbriquées, les digraphes aléatoires, et les digraphes aléatoires r-réguliers.
Nous nous intéressons aussi aux relations entre le nombre dichromatique et autres paramètres, comme le degré maximal et le nombre de biclique. En particulier, nous montrons qu'une version orientée de la conjecture de Borodin–Kostochka est valide pour des grands degrés maximaux, ce qui
généralise un résultat de Reed.
Finalement, nous ajoutons quelques considérations sur les variantes circulaire, fractionnaire, et de liste du problème.