Erdös-Pósa properties

• Applicant: Professor Dr. Henning Bruhn-Fujimoto
• Subject Area: Mathematics
• Term: from 2016 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 321904558

• Final Report Year: 2021

Final Report Abstract

In graph theory, we often look for many disjoint instances of some target graphs in a host graph. For instance, we might look for many disjoint cycles in a given graph; this is then called a packing of cycles. Not every graph will contain a large packing: for example, a graph that admits a small covering, a vertex set that meets all target graphs, will not contain a large packing. For some target graphs (eg, cycles) there will always be a dichotomy between packing and covering: every host graph has either a large packing or a small covering. For other target graphs (eg, odd cycles) there are host graphs that have neither: no large packing and no small covering. In this project, we have investigated the interplay between packing and cov- ering. A particular focus was on the edge-variant of this interplay, where instead of (vertex-)disjoint target graphs we seek merely edge-disjoint target graphs, and where instead of a covering consisting of vertices we only admit coverings of edges. That packing and covering in the normal and in the edge-variant behave very differently is the main insight of this project. (There were signs pointing to similar behaviour.)

Publications

• Packing A-Paths of Length Zero Modulo Four
  H. Bruhn and A. Ulmer
  (See online at https://doi.org/10.48550/arXiv.1805.08673)
• Erdös-Pósa property for labelled minors: 2-connected minors, SIAM Disc. Math.
  H. Bruhn, F. Joos and O. Schaudt
  (See online at https://doi.org/10.48550/arXiv.1805.00426)
• Erdös-Pósa from Ball Packing. SIAM Disc. Math. 34 (2020), 1609–1619
  W. Cames van Batenburg, G. Joret, and A. Ulmer
  (See online at https://doi.org/10.1137/19m1309225)
• The edge-Erdös-Pósa property. Combinatorica (2020)
  M. Heinlein and F. Joos
  (See online at https://doi.org/10.48550/arXiv.1809.11038)
• Zero A-paths and the Erdös-Pósa property
  A. Ulmer
  (See online at https://doi.org/10.48550/arXiv.2010.00663)
• K4 -subdivisions have the edge-Erdös-Pósa property. SIAM Disc. Math. 35 (2021), 392–430
  H. Bruhn and M. Heinlein
  (See online at https://doi.org/10.1137/18m1216511)