Digraphs – DIGRAPHS

Our methodology is two-fold. On the first hand, we will consider many results on graphs, find their (possibly many) formulations in terms of digraphs and see if and how they can be extended. On the second hand, we will focus on the tools. We believe that many proof techniques have been too rarely used or adapted to digraphs and can be developed to obtain many more results.

We worked on some digraphs problems and made a number of advancces on different aspects of those.

Firstly, we developed and introduced some proof methods for digraphs, such as median orders, oriented matroids, and twin-width.

Secondly, we studied how some problems, in particular graph partition problems can be generalized to digraphs. We mainly focused on graph colouring problems.

Finally, we studied how to practically solve some digraph problems arising from apllications. In particcular, we focused on disjoint or dissimalr paths problems coming from multimodal transportation or networks.

We will pursue the on-going studies while increasing the collaboration between partners, which has been very limited due to the sanitary crisis.

12 articles in international journals.
9 articles in international conferences.
1 article in a national conference.

Directed graph (a.k.a. digraph) theory is a lot less developed than (undirected) graph theory and there is a lack of algorithmically meaningful structural theory for digraphs. The objectives of the project is to make some advances on digraph theory in order to get a better understanding of important aspects of digraphs and to have more insight on the differences and the similarities between graphs and digraphs.
Our methodology is two-fold.

On the one hand, we will consider results on graphs, find their (possibly many) formulations in terms of digraphs and see if and how they can be extended. Studying such extensions has been occasionally done, but the point here is to do it in a kind of systematic way. We will mainly focus on substructures in digraphs (complexity and conditions of existence) and extensions of graph colouring problems to digraphs.

On the other hand, we will focus on the tools. We believe that many proof techniques have been too rarely used or adapted to digraphs and can be developed to obtain many more results. This in particular the case of median and cyclic order, the canonical decomposition of digraphs arising from matroids, the different notions of treewidth for digraphs, structural decomposition theorem, entropy compression and VC-deimension.

Of course, those two approaches are not mutually exclusive but converge. Our goal is to develop the techniques to make advances in the above mentioned topics.