Digraphes – DIGRAPHS

La méthodologie est double. D’une part, nous étudions les techniques de preuves qui n’ont que trop rarement été adaptées aux digraphes. D’autre part, nous explorerons comment des résultats sur les graphes non-dirigés peuvent s’étendre aux digraphes, notamment ceux en coloration de graphes.

Comme prévu nous avons travaillé sur les problèmes de digraphes et fait un certain nombre d’avancées sur des aspects différents de ceux-ci.

D’une part, nous avons développé et introduit des méthodes de preuves pour les digraphes, comme les ordres médians, les matroides orientés et la twin-width.

D’autre part, nous avons étudié comment certains problèmes, en particulier les problèmes de partitions de graphes peuvent se généraliser aux digraphes. Comme prévu l’accent a été donné aux problèmes de coloration.

Enfin, nous avons également étudié comment résoudre pratiquement des problèmes de digraphes issus d’applications. En particulier, nous nous sommes focalisés sur des problèmes de chemins disjoints ou dissimilaires issus de problèmes de transport multimodaux et de réseaux.

Poursuite des travaux effectués en augmentant fortement la collaboration entre les partenaires qui a été très limitées par la crise sanitaire.

12 articles dans des revues internationales.
9 articles dans des conférences internationales.
1 article dans une conférence nationale

La the´orie des graphes dirige´s (digraphes) est bien moins de´veloppe´e que celle des graphes et il manque de the´orie structurelle des digraphes qui soit algorithmiquement utile. Le but de ce projet est de faire des avance´es en the´orie des digraphes afin de mieux comprendre certains de leurs aspects importants et de mieux comprendre les diffe´rences et les similarite´s entre graphes et digraphes.
Notre me´thodologie a deux axes.

D'un co^te´, nous conside´rerons des proble`mes de graphes, trouverons leurs formulations en terme de digraphes et verrons s'ils peuvent e^tre e´tendus et comment. L'e´tude de telles extensions a e´te´ occasionnellement faite, mais l'ide´e ici est de le faire de fac¸on syste´matique. Nous nous concentrerons plus particulièrement sur les problèmes de sous-structures (complexité et conditions d'existence) ainsi que les généralisations des théorèmes de coloration aux digraphes.

D'un autre co^te´, nous nous concentrerons sur les outils.
Nous croyons que de nombreuses techniques n'ont e´te´ que trop rarement utilise´es ou adapte´es aux digraphes et peuvent e^tre de´veloppe´es pour obtenir de nombreux re´sultats. C'est en particulier le cas des ordres médians et cycliques, de la décomposition canonique issue des matroides, des différentes notions de largeur arborescente pour les digraphes, des théorèmes de décomposition structurels, de la compression d'entropie et de la VC-dimension.

Evidemment, ces deux axes ne sont pas exclusifs mais convergent. Notre but est de développer les techniques pour obtenir des avancées sur les thématiques évoquées plus haut.