Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 ...