Description

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.

Compétences requises

Le/la candidat(e) doit posséder une formation en mathématiques discrètes, combinatoire ou algorithmique. Une connaissance préalable en théorie des graphes est un plus. Sont attendues : autonomie scientifique, capacité à travailler sur des problèmes théoriques ouverts, bonnes compétences rédactionnelles en anglais, et goût pour la recherche fondamentale.

Bibliographie

Kreutzer, Oum, Seymour, van der Zypen, Wood — Majority Colourings of Digraphs, Electron. J. Combin. (2017).

Girão, Kittipassorn, Popielarz, Tait — Generalised Majority Colourings of Digraphs, CPC (2017).

Anastos, Lamaison, Steiner, Szabó — Majority Colorings of Sparse Digraphs, Electron. J. Combin. (2021).

Mots clés

coloration majoritaire, graphes orientés, combinatoire, méthodes probabilistes, tournois, optimisation