| Resumé |
Les réseaux sont omniprésents dans notre vie quotidienne, que ce soit des réseaux sociaux, des réseaux de neurones ou des réseaux routiers. Pourtant, les graphes, leur pendant théorique, sont utilisés depuis des siècles pour modéliser des problèmes pratiques. Un graphe est un ensemble de sommets reliés par des arêtes. Si on considère des arêtes orientées, on parlera plutôt de digraphes. L'un des concepts les plus féconds de la théorie des graphes (appliqué aussi bien à des problèmes d'allocation de registres qu'à l'attribution de fréquences radio) est la coloration de graphes, qui consiste à attribuer des couleurs aux sommets de manière à ce que les sommets adjacents aient des couleurs distinctes. Le nombre chromatique d'un graphe est alors le nombre minimum de couleurs nécessaires. Cette thèse s'intéresse au nombre dichromatique, une métrique introduite en 1982 par Neumann-Lara comme équivalent du nombre chromatique, mais pour les digraphes. Colorer un digraphe, c'est attribuer une couleur à chacun de ses sommets de sorte qu'aucun cycle dirigé ne soit monochromatique, et le nombre dichromatique d'un digraphe est le nombre minimum de couleurs nécessaires. Des résultats récents suggèrent que cette métrique est la bonne notion de coloration dans le cas dirigé. Le but de cette thèse est d'étudier comment la structure d'un digraphe affecte son nombre dichromatique. Dans la première partie de ce travail, nous examinons comment le nombre dichromatique interagit avec d'autres métriques. Tout d'abord, nous considérons le degré, c'est-à-dire le nombre maximum de voisins d'un sommet. Dans le cas non dirigé, cela correspond au théorème de Brooks, un théorème célèbre avec de nombreuses variations et généralisations. Dans le cas des digraphes, il n'existe pas de métrique naturelle correspondant au degré maximal. Nous étudions donc comment différentes notions de degré conduisent soit à des théorèmes de type Brooks, soit à des résultats d'impossibilité. Nous étudions également l'arc-connectivité maximale, une métrique plus générale, fournissons un théorème semblable au théorème de Brooks pour cette métrique ainsi qu'un algorithme polynomial pour reconnaître les cas extrêmaux.La deuxième partie de ce manuscrit se concentre sur un analogue dirigé de la conjecture de Gyarfas-Sumner, qui essaie de caractériser les ensembles S de graphes tels que les graphes ayant un nombre chromatique suffisamment grand contiennent un graphe de S. Cette conjecture reste largement ouverte. Pour les digraphes, une conjecture correspondante a été proposée par Aboulker, Charbit et Naserasr. Nous prouvons plusieurs cas de cette conjecture, principalement en démontrant que certaines classes de digraphes ont un nombre dichromatique borné. Par exemple, nous prouvons que les graphes orientés quasi-transitifs et localement out-transitifs ont un petit nombre dichromatique. Nous caractérisons également les digraphes qui doivent apparaître dans les orientations des graphes multipartites complets avec un nombre dichromatique suffisamment grand et, ce faisant, nous découvrons un contre-exemple à la conjecture initiale d'Aboulker, Charbit et Naserasr. Nous obtenons des résultats similaires pour les digraphes sans triangle et sans chemins dirigés sur six sommets, ainsi que pour les orientations des graphes cordaux. Dans la dernière partie de cette thèse, nous abordons le problème de l'arête-coloriage d-défectueux, qui consiste à colorer les arêtes d'un multigraphe de telle sorte que, pour tout sommet, aucune couleur n'apparaisse sur plus de d de ses arêtes incidentes. Lorsque d est égal à un, cela correspond au problème de l'arête-coloration. Shannon a trouvé une borne stricte sur le nombre de couleurs nécessaires par rapport au degré maximal lorsque d est égal à un, et nous étendons ce résultat à toute valeur de d. Nous explorons également ce problème sur des graphes simples et prouvons des résultats qui étendent le théorème de Vizing à toute valeur de d. |