ANR Project DAGDigDec (DAGs and Digraph Decompositions) - ANR-21-CE48-0012
In this project we aim to study certain fundamental structures of directed graphs.
A central notion appearing in the study of digraphs is that of a Directed Acyclic Graph (or DAG),
a digraph without directed cycles. It is hard to overstate the role that DAGs play in computer science and discrete mathematics. Their applications in telecommunications, sorting, scheduling, data compression, and data processing are ubiquitous.
Curiously enough, compared to their practical importance, fundamental knowledge and understanding of DAGs is not as broad or deep as one would like. The main goal of this project is to study how DAGs affect the structure and properties of digraphs
which contain them, thus giving us insight into general understanding of arbitrary digraphs.
A related important problem is decomposing a general digraph into DAGs. In classical graph theory,
such decompositions often lead to efficient algorithms. Here, given a general digraph D on n vertices, one would like to partition the vertices of D into, say, k parts such that the vertices of each part induce a DAG.
The minimum integer k for which this can be done is defined to be the dichromatic number of D.
Dichromatic theory is now a well-studied area
and this project also aims to increase our understanding of this parameter.
Members of the Project
| Permanent Members
|| Non-permanent Members
- Pierre Aboulker, ENS Paris
- Julien Bensmail, Sophia-Antipolis, Nice
- Nicolas Bousquet, University of Lyon 1
- Ararat Harutyunyan (PI), University Paris Dauphine
- Kolja Knauer, University of Barcelona/Aix-Marseille
- Alantha Newman, University Grenoble
- Petru Valicov, University of Montpellier
- Gil Puig i Surroca (PhD student), University Paris Dauphine
- Nikolaos Melissinos (PhD student), University Paris Dauphine
- Guillaume Aubian (PhD student), ENS Paris
A. Harutyunyan, M. Lampis, N. Melissinos,
Digraph Coloring and Distance to acyclicity , STACS 2021.
P. Aboulker, F.Havet, K. Knauer, C. Rambaud, On the dichromatic number of surfaces, Electronic Journal of Combinatorics, 2022.