PhD defense of Lucas Picasarri-Arrieta

• Marthe Bonamy, CRCN CNRS, LaBRI, Bordeaux, France
• Louis Esperet (referee), DR CNRS, INP Grenoble, France
• Ararat Harutyunyan, MCF, Université Paris-Dauphine, France
• Alexander Scott (referee), Professor, University of Oxford, UK
• Stéphan Thomassé, Professor, ENS Lyon, France
• Anders Yeo (referee), Professor, University of Southern Denmark
• Frédéric Havet (supervisor), DR CNRS, COATI, France
• Stéphane Bessy (co-supervisor), Professor, LIRMM, University of Montpellier, France

Abstract: This thesis focuses on a notion of colouring of digraphs introduced by Erdös and Neumann-Lara in the late 1970s, namely the dicolouring, and its associated digraph parameter: the dichromatic number. It appears in the last decades that many classical results on graph colouring have directed counterparts using these notions.
We first give a collection of bounds on the dichromatic number of digraphs for which the underlying graph is chordal. We then introduce a notion of variable degeneracy for digraphs which leads to a more general version of Brooks Theorem. We also strengthen this theorem on a large class of digraphs which contains digraphs without antiparallel arcs.
Next we prove a collection of results on $k$-dicritical digraphs, the digraphs that are minimal obstructions for the $(k-1)$-dicolourability. We first generalise a result of Gallai to the directed case, and then prove a conjecture of Kostochka and Stiebitz in the particular case $k=4$. We also discuss the maximum density of such digraphs and prove that the number of $3$-dicritical semi-complete digraphs is finite. We then give a collection of results on the substructures in large dicritical digraphs.
We finally study the notion of redicolouring for digraphs. In particular, we prove that a large collection of evidences for Cereceda’s conjecture admit a directed counterpart.

Résumé: Cette thèse est dédiée à l’étude de la dicoloration, une notion de coloration pour les digraphes introduite par Erdös et Neumann-Lara à la fin des années 1970, ainsi que le paramètre qui lui est associé, à savoir le nombre dichromatique. Lors des dernières décennies, ces deux notions ont permis de généraliser de nombreux résultats classiques de coloration de graphes.
Nous commençons par donner différentes bornes sur le nombre dichromatique des digraphes dont le graphe sous-jacent est un graphe cordal. Ensuite, nous améliorons la borne donnée par le théorème de Brooks pour les digraphes sans arcs antiparallèles et introduisons une notion de dégénérescence variable pour les digraphes, ce qui nous permet de prouver une version plus générale du théorème de Brooks.
Nous étudions ensuite les digraphes $k$-dicritiques, c’est-à-dire les obstructions minimales à la $(k-1)$-dicolorabilité. En particulier, nous généralisons un résultat de Gallai au cas dirigé, et nous prouvons une conjecture de Kostochka et Stiebitz dans le cas particulier $k=4$. Nous discutons également la densité maximum de tels digraphes, et prouvons qu’il n’y a qu’un nombre fini de digraphes semi-complets $3$-dicritiques. On donne par la suite certains résultats structurels sur les digraphes dicritiques de grand ordre.
Enfin, nous étudions la notion de redicoloration pour les digraphes. En particulier, nous prouvons que de nombreux résultats soutenant la conjecture de Cereceda se généralisent au cas dirigé.