Lucas Picasarri-Arrieta

Coloration de graphes dirigés: Cette thèse est dédiée à l'étude de la dicoloration, une notion de coloration pour les digraphes introduite par ErdH{o}s et Neumann-Lara à la fin des années 1970, ainsi que le paramètre qui lui est associé, à savoir le nombre dichromatique. Au cours 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 variables 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é.

In this paper we consider the following three coloring concepts for digraphs. First of all, the generalized coloring concept, in which the same colored vertices of a digraph induce a subdigraph that satisfies a given digraph property. Second, the concept of variable degeneracy, introduced for graphs by Borodin, Kostochka and Toft in 2000; this allows to give a common generalization of the point partition number and the list dichromatic number. Finally, the DP-coloring concept as introduced for graphs by Dvořák and Postle in 2018, in which a list assignment of a graph is replaced by a cover. Combining these three coloring concepts leads to generalizations of several classical coloring results for graphs and digraphs, including the theorems of Brooks, of Gallai, of Erdős, Rubin, and Taylor, and of Bernshteyn, Kostochka, and Pron for graphs, and the corresponding theorems for digraphs due to Harutyunyan and Mohar. Our main result combines the DP-coloring and variable degeneracy concepts for digraphs.

A digraph is $3$-dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that the collection of 3-dicritical semi-complete digraphs is finite. Further, we give a computer-assisted proof of a full characterization of 3-dicritical semi complete digraphs. There are eight such digraphs, two of which are tournaments. We finally give a general upper bound on the maximum number of arcs in a $3$-dicritical digraph.

The dichromatic number of a digraph is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph. A digraph is ‐dicritical if and each proper subdigraph of satisfies . For integers and , we define (resp., ) as the minimum number of arcs possible in a ‐dicritical digraph (resp., oriented graph). Kostochka and Stiebitz have shown that . They also conjectured that there is a constant such that for and large enough. This conjecture is known to be true for . In this work, we prove that every 4‐dicritical oriented graph on vertices has at least arcs, showing the conjecture for . We also characterise exactly the 4‐dicritical digraphs on vertices with exactly arcs.