Quelques sujets sur la coloration des graphes orientés

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.