![]() |
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, 2024. |
![]() |
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 (until December 2018)
- Thomas Bellitto (From August 2018 to February 2020 as a Post Doc)
- Tilde My Christiansen (PhD student until December 2018)
- Kristine Vitting Klinkby Knudsen (Cotutelle PhD student between University of Bergen and SDU) until August 2021. Kristine continued in the project as a postdoc until December 2022 (she was hired for a muchg shorter period as she was on maternal leave).
- Yun Wang (PhD student from December 1, 2021 till November 30, 2023. Yun Wang is hired as research assistant (post doc) from November 1, 2023 till December 31, 2023.
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 was hired for 18 months starting in August 2018 and shorter terms postdocs Kristine Vitting Klinkby Knudsen and Yun Wang, the activities on this grant are research related traveling to conferences, meetings by invitation, research collaboration, and hosting guests.
Research visits and other external activities by members of the grant
2018
- January 7-10, 2018: Kristine V.K. Knudsen participated in the 29th SODA in New Orleans USA where she gave the lecture 'Parameterized Algorithms for Survivable Network Design with Uniform Demands'.
- January 2018: Bang-Jensen visited LIRMM, Universite Montpellier for two weeks to work with Stephane Bessy
- February-May 2018: Kristine V.K. Knudsen visited University of Bergen for 4 months as part of her cotutelle PhD (which started September 2017)
- 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.
- August 29-September 1, 2018 Bang-Jensen and Bjarne Toft organized the conference GT2018 in Nyborg. Here Bellitto gave the talk ' Minimum connecting transition sets' and Kristine V.K. Knudsen gave the talk 'A parameterized algorithm for removing links from networks while maintaining connectivity constraints'
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.- January 12-January 19 2020: Anders Yeo visited Royal Holloway, University of London to work with Gregory Gutin.
- 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.
- July 27-July 31 2020: Anders Yeo attended the (online due to Covid-19) Workshop on Graph Theory and Combinatorics in Thuringia as one of 6 plenary speakers.
2021
Again due to the Covid-19 situation we have had very little travel.- August 20-27, 2021: Bang-Jensen visited LIRMM, Universite Montpellier to work with Stephane Bessy, Daniel Goncalves and Lucas Picassari-Arrietta.
- September 10, 2021: Bang-Jensen acted as the external opponent on the PhD thesis of Jonas Granholm at Linkoping University, Sweden.
2022
- June 30-July 15 Bang-Jensen visited LIRMM, Université Montpellier. July 4-8 he attended ICGT 2022 in Montpellier. He gave the talk ’Making a tournament k-strong by adding new arcs’. This is based on joint work with Anders Yeo and former Masters student Kasper Skov Johansen, now a research assistant at DTU Compute. Kasper will start his PhD studies at DTU later this fall. At ICGT Bang-Jensen also chaired the opening plenary talk by Reinhard Diestel. While in Montpellier, Bang-Jensen also visited his research collaborator Stephane Bessy at LIRMM Université Montpellier https://www.lirmm.fr/~bessy/ They continued their long term collaboration on the structure of directed graphs.
- July 3-July 9: Yun Wang attended ICGT 2022 in Montpellier. She gave the talk "Arc-disjoint in and out-branchings in co-bipartite digraphs"
- October 5-October 11: Bang-Jensen visited LRI, Universite Paris-Sud. On October 10 he was a main speaker at the one day meeting in the memory of Yannis Manoussakis. The topic of the talk was connections between digraphs and edge-coloured graphs.
- October 30-November 4 2022: Anders Yeo visited Royal Holloway, University of London to work with Gregory Gutin.
2023
- May 16-May 28 Bang-Jensen visited team Coati, INRIA Sophia Antipolis to work with Lucas Picasarri-Arietta.
- May 29-June 4 Bang-Jensen and Anders Yeo attended the ANR Digraphs workshop in Sete, France and gave the invited lectures "Open problems on digraphs" and "Directed max-cut and some generalizations", respectively.
- June 18-June 24: Anders Yeo attended the 10th Slovenian Conference on Graph Theory as a plenary speaker. His talk was "Directed max-cut and some generalizations".
- July 3-July 7: Anders Yeo attended the 29th Nordic Congress of Mathematicians in Aalborg, Denmark. He gave a talk in one of the sessions on graph theory.
- July 29-August 16 Bang-Jensen visited Department of Mathematics and Statistics, University of Victoria to work with Jing Huang.
- August 13-August 20: Anders Yeo visited Nankai University in China.
2024
- April 19-24, 2024: Anders Yeo visited Nankai University in China.
- May 8, 2024: Bang-Jensen attended 'Barc celebration' at Copenhagen Univeristy.
- June 17-20, 2024: Anders Yeo visited INRIA Sophia Antipolis as external examinator on the PhD degree of Lucas Piccassario-Arietta.
- August 29-September 20, Bang-Jensen visited Department of Mathematics and Statistics, University of Victoria to work with Jing Huang.
- September 26-October 25: Bang-Jensen visited INRIA Sophia Antipolis to work with several people from project Coati, including Frederic Havet, Florian Hoersch and Clement Rambaud.
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.
2021
Due to Covid-19 most of our planned visitors had to be canceled- July-September 2021: 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 3 weeks at SDU.
2022
- July-September 2022: Michael Stiebitz, Department of Mathematics, Technische Universitat Ilmenau, visited us at SDU for 3 months.
- August 21-26 2022: Yubao Guo, RWTH Aachen, visited us and gave the talk: Extensions of Moon's and Alspach's theorems on tournaments to multipartite tournaments.
- August 28-September 3 2022: Florian Hörsch, TU-Ilmenau, visited us and gave the talk: Orientations and connectivity.
- August 21-September 1 2022: Michael Henning, University of Johannesburg, South Africa visited Anders Yeo in Amsterdam (as Anders lives there).
2023
- January 15-20: Florian Hörsch, TU-Ilmenau, visited us.
- April 24-May 1: Michael Henning, University of Johannesburg, South Africa visited Anders Yeo in Amsterdam (as Anders lives there).
- June-August: Michael Stiebitz, Department of Mathematics, Technische Universitat Ilmenau, visited us for 3 months.
- September 20- October 1: Michael Stiebitz, Department of Mathematics, Technische Universitat Ilmenau, September 24-October 1, Lucas Picasarri-Arietta, INRIA, Sophia Antipolis, France visited us.
- December 10- December 15: Stephane Bessy, LIRMM Universite Montpellier visited us.
- December 9-December 16: Michael Henning, University of Johannesburg visited us.
2024
- January 30- February 3, 2024: Gregory Gutin, Royal Holloway University of London visited us
- June-September, 2024: Michael Stiebitz, TU-Ilmenau visited us.
- May 25-June 3, 2024: Michael Henning, University of Johannesburg, South Africa visited Anders Yeo in Amsterdam (as Anders lives there).
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 a 30 hour course on Directed graphs as part of the summerschool on Graph theory at Shandong University in China link to info about the course
- March 17-18, 2021: Bang-Jensen gave two online presentations on good acyclic orientations of graphs to researchers at Shandong University in China.
- November 26, 2021: Kristine Vitting Klinkby Knudsen succesfully defended her PhD Thesis, Parameterized problems on (Di)graphs. She will receive a cotutelle PhD degree from University of Bergen and University of Southern Denmark.
- July 3-7, 2023: Bang-Jensen gave a 30 hour online course on Directed graphs as part of the summerschool on Graph theory at Shandong University in China
- February 2, 2024: Yun Wang successfully defended her PhD thesis, Structural and algorithmic properties concerning packing, covering and partitioning of digraphs.
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. - Chapter 1 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
- 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. - Chapter 2 in 'Classes of Directed Graphs', Bang-Jensen and Gutin (eds)
- 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.
- Transversals in linear uniform hypergraphs.
- Michael Henning and Anders Yeo
Springer (ISBN 978-3-030-46558-2) 2020.
- Domination and Total Domination in Hypergraphs
- Michael Henning and Anders Yeo
Chapter in "Structures of Domination in Graphs, Haynes, Hedetniemi and Henning (eds)
Volume 66 in Springer book series on Developments in Mathematics 2021
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.
Journal of Graph Theory 87: 285-304 (2018).
Journal of Graph Theory 87: 285-304, 2018.
Journal of Graph Theory 89: 304-326, 2018.
Journal of Graph Theory 89: 115-149, 2018.
Electronic J. Combin. 25(4): P4.27, 2018.
Discrete Mathematics & Theoretical Computer Science 20(2) (2018)
Eur. J. Comb. 78 1-12 (2019)
Theoretical Computer Science 776: 64-74, 2019.
Journal of Graph Theory 92: 130-151, 2019.
Journal of Graph Theory 92: 5-18, 2019.
Theoretical Computer Science 795: 108-114, 2019.
Journal of Graph Theory 93: 88-112, 2020.
Journal of Graph Theory 95: 76-98, 2020.
Electronic J. Combinatorics 27(1): P1.63, 2020.
Theoretical Computer Science 814: 69-73, 2020.
J. Combinatorial Optimization39(1): 77-99, 2020.
Journal of Graph Theory95(2) 267-289 2020
Discrete Mathematics343(12) 112129 (2020).
Theoretical Computer Science 844: 69-73 (2020)
Journal of Graph Theory96(1): 137-159 (2021)
Journal of Graph Theory 96: 594-618 (2021).
Graphs and Combinatorics 37(3): 867-890 (2021).
Discuss. Math. Graph Theory 41(1) 123-132 (2021).
Discrete Math. 344(8) 112438 (2021).
Graphs and Combinatorics 37(6) 2601-2620 (2021).
Discrete Appl. Math. 302 1-7 (2021).
Discrete Appl. Math. 304 12-22 (2021).
Algorithmica 84(9) 2767-2784 (2022).
Discrete Mathematics 345(6) 112831 (2022).
J. Graph Theory 99(4) 615-636 (2022).
J. Graph Theory 100(2) 294-314 (2022).
J. Graph Theory 100(4) 698-720 (2022).
Siam J. Disc. Math 36(1) 578-595 (2022).
Theoretical Computer Science 928 167-182 (2022).
J. Graph Theory99 615-636 (2022).
Graphs Comb.38 187 (2022).
J. Graph Theory101 643-667 (2022).
Theor. Comput. Sci. 973 114097 (2023).
Theor. Comput. Sci949 113758 (2023).
J. Graph Theory102 578-606 (2023).
Discret. Appl. Math 332 155-169 (2023).
Discret. Appl. Math 340 259-271 (2023).
Discret. Math. 346 113435 (2023).
Expert Syst. Appl. 213 118864 (2023).
Games Econ. Behav. 141 529-457 (2023).
J. Graph Theory 102 86-106 (2023).
Discret. Math. 1142-1161 (2023).
Theor. Comput. Sci. 940 222-230 (2023).
SIAM J. Disc. Math. 37 1275-1310 (2023).
Theor. Comput. Sci. 1010: 114702 (2024).
Eur. J. Comb. 120: 103981 (2024).
Discret. Appl. Math. 346: 215-227 (2024).
J. Graph Theory 106 (1) 182-197 (2024).
J. Graph Theory online November 2024 https://doi.org/10.1002/jgt.23199
Discret. Math. 347(10): 114126 (2024).
Games Econ. Behav. 148: 244-263 (2024).
J. Graph Theory 105(3): 413-426 (2024).
J. Graph Theory 105(3): 468-485 (2024).
SIAM J. Discret. Math. 38(3): 2370-2391 (2024).
Discret. Comput. Geom. 71(2): 358-398 (2024).
Peer-Reviewed International Conference Articles
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.]
IPEC 2020: 2:1-2:16 (2020)
ALGOS 2020 101-121 2020. dt>
COCOON 2020360-371 (2020)
ESA 2021 11.1-11.15 2021.
SODA: 219-234, SIAM, 2021.
MFCS 2021:54:1-54:13, 2021
IJCAI: 2023.
ESA 2023 13.1-13.15 2023.