The project 'Packing, covering and partitions of digraphs' is funded by the DKK 2,592,000 grant DFF-7014-00037A from the Independent Research Fund Denmark, Natural Sciences, running from January 1, 2018 through December 31, 2020.
The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark.

Participants

Environment

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The participants are all associated with the Research Training Programs in Mathematics and Computer Science as Ph.D. advisors.

Activities

Besides supervision of one postdoc, Thomas Bellitto, who is hired for 18 months starting in August 2018, the activities on this grant are research related traveling to conferences, meetings by invitation, research collaboration, and hosting guests.

Short Project description

The project deals with structural and algorithmic aspects of problems related to packing, coverings or partitions in digraphs and generalizations of digraphs such as edge-coloured graphs. Examples are: packing cycles, linkage problems, packing strong subdigraphs, branchings, vertex partitions with prescribed properties in (di)graphs, packing sub(di)graphs in digraphs, edge-coloured graphs, completing partial orientations of graphs to obtain digraphs with prescribed properties.

Publications

Here we list project related publications by members of the group since January 1, 2018.

Books and chapters in books

Classes of Directed Graphs.
Jørgen Bang-Jensen, Gregory Gutin (editors)
Springer Monographs in Mathematics, 2018.
Basic Terminology, Notation and Results.
Jørgen Bang-Jensen, Gregory Gutin
Chapter 1 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.
Tournaments and Semicomplete digraphs.
Jørgen Bang-Jensen, Frederic Havet
Chapter 2 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.
Locally Semicomplete digraphs and Generalizations.
Jørgen Bang-Jensen
Chapter 6 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.
Semicomplete Multipartite Digraphs.
Anders Yeo
Chapter 7 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
Springer Monographs in Mathematics, 2018.

Peer-Reviewed International Journal Articles

Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs.
Michael A. Henning, Anders Yeo:
Discrete Mathematics 341(8): 2285-2292 (2018)
Degree constrained 2-partitions of semicomplete digraphs.
Jørgen Bang-Jensen, Tilde My Christiansen
Theoretical Computer Science 746: 112-123 (2018)
Out-degree reducing partitions of digraphs.
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo.
Theoretical Computer Science 719: 64-72, 2018.

Chi-bounded families of oriented graphs.
Pierre Aboulker, Jørgen Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, Frédéric Maffray, José Zamora.
Journal of Graph Theory 87: 285-304 (2018).

Completing orientations of partially oriented graphs.
Jørgen Bang-Jensen, Jing Huang, Xuding Zhu.
Journal of Graph Theory 87: 285-304, 2018.

Bipartite spanning sub(di)graphs induced by 2-partitions.
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo.
Journal of Graph Theory to appear.

Tight lower bounds on the matching number in a graph with given maximum degree
Michael A. Henning and Anders Yeo.
Journal of Graph Theory 89: 115-149, 2018.

Peer-Reviewed International Conference Articles


Parameterized Algorithms for Survivable Network Design with Uniform Demands.
Jørgen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi:
SODA: 2838-2850, SIAM, 2018.
[Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018.]