Thèse Coloration Majoritaire dans les Graphes Orientés H/F - 75

Établissement : Institut Polytechnique de Paris Télécom SudParis
École doctorale : Ecole Doctorale de l'Institut Polytechnique de Paris
Laboratoire de recherche : SAMOVAR - Services répartis, Architectures, Modélisation, Validation, Administration des Réseaux
Direction de la thèse : Walid BEN-AMEUR ORCID 0000000328651123
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-06-01T23:59:59

Une coloration majoritaire dans un graphe orienté est une coloration dans lesquelles chaque sommet partage sa couleur avec au plus la moitié de ses voisins sortants. Un résultat fondamental établit que tout graphe orienté admet une coloration majoritaire à quatre couleurs. Le principal problème ouvert du domaine, posé par Kreutzer, Oum, Seymour, Van der Zypen et Wood, est de déterminer si trois couleurs suffisent toujours.
L'objectif de cette thèse est de développer de nouvelles techniques combinatoires, probabilistes et structurelles pour progresser vers la résolution de cette conjecture, tant dans le cas général que pour des classes importantes telles que les tournois. Des avancées récentes montrent qu'une large variété de graphes - notamment les graphes clairsemés ou de faible complexité structurelle - sont déjà coloriables avec trois couleurs selon la condition majoritaire. Dans les tournois, des résultats récents allient probabilités, inégalités de concentration et optimisation linéaire pour réduire drastiquement le nombre de sommets pouvant violer la contrainte majoritaire.
Le doctorant explorera plusieurs axes : renforcement des techniques probabilistes, développement de méthodes structurales basées sur la décomposition et la dichromaticité, analyse fine des tournois, et extensions vers les variantes list-coloring ou fractionnaire. Les objectifs incluent l'obtention de nouveaux résultats pour les classes structurées, la réduction ou l'élimination des sommets exceptionnels dans les tournois, et la conception de méthodes hybrides combinant probabilités et optimisation.
Même des progrès partiels seraient des contributions significatives en combinatoire moderne.

La coloration majoritaire s'inscrit dans la combinatoire probabiliste et la théorie des graphes orientés. Malgré des avancées importantes, la question de l'existence d'une coloration majoritaire à trois couleurs reste ouverte. Les approches actuelles combinent inégalités de concentration, lemme local de Lovász, recolorations aléatoires et optimisation linéaire. Les tournois constituent une classe clé permettant d'affiner ces méthodes. Le contexte scientifique est donc riche, actif et en pleine évolution.