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, 2021. | |

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. |

## Participants

- Jørgen Bang-Jensen (PI)
- Anders Yeo
- Marco Chiarandini
- Thomas Bellitto (From August 2018 to February 2020 as a Post Doc)
- Tilde My Christiansen (PhD student until December 2018)
- Kristine Vitting Klinkby Knudsen (PhD student until June 2021)

## 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.

### Research visits by members of the grant

## 2018

- January 2018: Bang-Jensen visited LIRMM, Universite Montpellier for two weeks to work with Stephane Bessy
- May 2018: Bang-Jensen visited LIRMM, Universite Montpellier for two weeks to work with Stephane Bessy.
- June 2018: Bang-Jensen visited INRIA project team Coati for one week to work with Frederic Havet
- June 11-15, 2018: Bang-Jensen participated in SGT2018 in SETE, France.
- June 26-29, 2018: Bang-Jensen participated in DMD2018 in Sevilla, Spain.
- July 8-11, 2018: Marco Chiarandini participated in EURO 2018 in Valencia Spain. Marco gave a talk entitled 'Course Timetabling in a Flexible Semester Structure'
- August 4-10, 2018: Bang-Jensen visited Simon Fraser University, Burnaby B.C., Canada to work with Pavol Hell.
- August 10-19, 2018: Bang-Jensen visited University of Victoria, Victoria BC, Canada to work with Jing Huang.
- August 26-28, 2018: Bang-Jensen visited LABRI, Universite Bordeaux, France as a member of the PhD committee of Thomas Bellitto.

## 2019

- January 7-12, 2019 Bang-Jensen visited INRIA project team Coati to work with Frederic Havet.
- January 12-18, 2019 Bang-Jensen visited LIRMM, Universite Montpellier for two weeks to work with Stephane Bessy.
- May 21-25, 2019 Bang-Jensen visited LIRMM, Universite Montpellier to work with Stephane Bessy.
- May 25-29, 2019 Bang-Jensen visited INRIA project team Coati to work with Frederic Havet.
- May 28-31, 2019 Bellitto attended CanaDAM 2019 in Vancouver and gave the talk 'Connecting edge-colouring'.
- May 31-June 16 Bellito visited Department of Mathematics and Statistics at University of Victoria to work with Gary MacGillivray.
- June 24-28, 2019: Bellitto attended "Structural graph theory workshop at Gułtowy, Poland"
- August 5-7, 2019: Bang-Jensen, Bellitto and Yeo participated in Norcom 2019 at Schaeffergaarden in Gentofte. Bang-Jensen gave the talk "Good acyclic orientations, antistrong digraphs and matroids" and Yeo gave the talk "Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments"
- August 25-September 2, 2019: Bang-Jensen visited, LIRMM, Universite Montpellier to work with Stephane Bessy and Dieter Rautenbach
- October 28-31, 2019, Bellitto attended the conference BGW 2019 in Bordeaux and gave the talk: “Connecting edge-colouring”
- November 13-15, 2019, Bellitto attended the conference JGA 2019 in Brussels and gave the talk: Hajós construction for digraphs”
- November 18-21, 2019, Yeo visited LIRMM Universite Montpellier to work with Stephane Bessy and as an external evaluator on the PhD thesis of Jocelyn Thiebaut

## 2020

Due to Covid-19 most of our travelplans had to be cancelled.- February 1-5, 2020 and February 11-20, 2020: Bang-Jensen visited INRIA project team Coati to work with Frederic Havet.
- February 5-11, 2020: Bang-Jensen visited LIRMM, Universite Montpellier to work with Stephane Bessy.
- February 25- June 10, 2020: Bang-Jensen visited INRIA project team Coati to work with Frederic Havet and others at INRIA. Unfortunately this part was heavily affected by Covid-19.

### Visits by collaborators

## 2018

- April 3-September 30, 2018: Michael Stiebitz, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU for 6 months.
- April 8-13,2018: Frederic Havet, INRIA, Sophia Antipolis visited us for one week at SDU and gave the talk 'Identifying codes in grids'.
- August 20-24, 2018: Stephane Bessy, LIRMM Universite Montpellier, France visited us at SDU.
- August 20-September 2nd: Mike Henning, University of Johannesburg, South Africa visited us at SDU.
- September 16-22, 2018: Matthias Kriesell, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU and gave the talk 'Certifying High Connectivity'.
- September 15-22, 2018: Thomas Schweser, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU.
- December 2-7, 2018, William Lochet, University of Bergen, Norway visited us and gave a talk entitled 'AVD coloring and entropy compression'.
- December 14-19, 2018, Jing Huang, Department of Mathematics and Statistics, University of Victoria visited us in connection with Tilde My Christansen's PhD defense.
- December 18-21, 2018 Gregory Gutin, Royal Holloway, University of London, visited us.

## 2019

- February 1 to March 31, 2019: Michael Stiebitz, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU for 2 months.
- February 12-28, 2019: Matthias Kriesell, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU
- March 5-15, 2019: Thomas Schweser, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU.
- May 3-July 15, 2019: Hugues Depres, ENS Lyon visited the group as part of his internship program at ENS.
- June 10-14, 2019: Stephane Bessy, LIRMM Universite Montpellier, France visited us at SDU.
- August 7-16, 2019: Kathie Cameron, Wilfried Laurier University, Canada visited us at SDU
- August 7-16, 2019: The world famous Jack Edmonds, Canada, one of the fathers of combinatorial optimization visited us at SDU.
- September 23-27, 2019, Mike Henning, University of Johannesburg, South Africa visited us at SDU and gave the talk: Matching and edge-connectivity in graphs with given maximum degree
- September 18-October 3, 2019, Matthias Kriesell, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU

## 2020

Due to Covid-19 most of our planned visitors had to cancel their visit.- July-September 2020: Michael Stiebitz, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU for 3 months.
- July 2020: Thomas Schweser, Department of Mathematics, Technische Universitat Ilmenau, visited us for one week at SDU.
- September 2020: Thomas Schweser, Department of Mathematics, Technische Universitat Ilmenau, visited us for weeks at SDU.
- September 27-October 3, 2020 Stephane Bessy, LIRMM Universite Montpellier, France visited us at SDU.

### Meetings arranged or co-arranged by the group

- August 29-September 1, 2018: Bang-Jensen and his college Bjarne Toft organized the conference GT2018 at Hotel Storebælt in Nyborg

### Other events

- December 17, 2018: Tilde My Christiansen successfully defended her PhD thesis, Algorithmic and structural problems in digraphs.
- July 6-10, 2020: Bang-Jensen gave an online course on Directed graphs as part of the summerschool on Graph theory at Shandong University in China link to info about the course

## 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.*

Michael A. Henning and Anders Yeo.

Jørgen Bang-Jensen, Stéphane Bessy

Jørgen Bang-Jensen, Stéphane Bessy, Frederic Havet, Anders Yeo

Jørgen Bang-Jensen, Kristine Vitting Klinkby, Saket Saurabh, Meirav Zehavi

Noga Alon, Jørgen Bang-Jensen, Stéphane Bessy

Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser, Michael Stiebitz

Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser, Michael Stiebitz

Jørgen Bang-Jensen, Thomas Bellitto, William Lochet, Anders Yeo.

Michael A. Henning, Anders Yeo

Jørgen Bang-Jensen, Thomas Bellitto, Anders Yeo

Jørgen Bang-Jensen, Gregory Gutin, Anders Yeo

Jørgen Bang-Jensen, Stephane Bessy, Jing Huang, Matthias Kriesell

Jørgen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi:

[Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018.]

Jørgen Bang-Jensen, Eduard Eiben, Gregory Gutin, Magnus Wahlstrom and Anders Yeo,

### 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)*

Pierre Aboulker, Jørgen Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, Frédéric Maffray, José Zamora.

Jørgen Bang-Jensen, Jing Huang, Xuding Zhu.

Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo.

Michael A. Henning and Anders Yeo.

Michael A. Henning and Anders Yeo.

**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.**

*Journal of Graph Theory*87: 285-304 (2018).

**Completing orientations of partially oriented graphs.**

*Journal of Graph Theory*87: 285-304, 2018.

**Bipartite spanning sub(di)graphs induced by 2-partitions.**

*Journal of Graph Theory*89: 304-326, 2018.

**Tight lower bounds on the matching number in a graph with given maximum degree**

*Journal of Graph Theory*89: 115-149, 2018.

**On upper transversals in 3-uniform hypergraphs**

*Electronic J. Combin.*25(4): P4.27, 2018.

**Complexity of locally-injective homomorphisms to tournaments**

*Stefan Bard, Thomas Bellitto, Christopher Duffy, Gary MacGillivray, Feiran Yang.*

Discrete Mathematics & Theoretical Computer Science20(2) (2018)

Discrete Mathematics & Theoretical Computer Science

**Upper transversals in hypergraphs**

*Eur. J. Comb.*78 1-12 (2019)

**Degree constrained 2-partitions of graphs.**

*Theoretical Computer Science*776: 64-74, 2019.

**Bipartite spanning sub(di)graphs induced by 2‐partitions**

*Journal of Graph Theory*92: 130-151, 2019.

**The parameterized complexity landscape of finding 2-partitions of digraphs**

*Theoretical Computer Science*795: 108-114, 2019.

**Out-colourings of digraphs**

*Journal of Graph Theory*93: 88-112, 2020.

**On DP-colourings of digraphs**

*Journal of Graph Theory*95: 76-98, 2020.

**Hajos and Ore Constructions for Digraphs**

*Electronic J. Combinatorics*27(1): P1.63, 2020.

**The directed 2-linkage problem with length constraints**

*Theoretical Computer Science*814: 69-73, 2020.

**Bounds on upper transversals in hypergraphs**

*J. Combinatorial Optimization*39(1): 77-99, 2020.

**Proper‐walk connection number of graphs**

*Journal of Graph Theory*2020, to appear.

**Arc‐disjoint strong spanning subdigraphs of semicomplete compositions**

*Journal of Graph Theory*2020, to appear.

**Good orientations of unions of edge-disjoint spanning trees**

*Journal of Graph Theory*2020, to appear.

### Peer-Reviewed International Conference Articles

**Parameterized Algorithms for Survivable Network Design with Uniform Demands.**

*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.]

**Component Order Connectivity in Directed Graphs**

*IPEC 2020, accepted.*