Erdös-Pósa-Eigenschaften

• Antragsteller: Professor Dr. Henning Bruhn-Fujimoto
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2016 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 321904558

• Erstellungsjahr: 2021

Zusammenfassung der Projektergebnisse

Oftmals in der Graphentheorie werden in einem gegebenen Graphen viele disjunkte Exemplare eines Zielgraphen gesucht, dies kann etwa eine Packung von Kreisen sein, eine Menge von disjunkten Kreisen. Nicht jeder gegebene Graph lässt eine große Packung zu, etwa, wenn eine kleine Uberdeckung vorliegt, eine Eckenmenge, die jeden Kreis im Graphen trifft. Für manche Arten von Zielgraphen (Kreise z.B.) liegt immer eines vor: eine große Packung oder eine kleine Überdeckung. Für andere Zielgraphen (ungerade Kreise etwa) ist dies nicht der Fall. Es gibt Graphen, die weder eine große Packung von ungeraden Kreisen noch eine kleine Überdeckung von ungeraden Kreisen enthalten. Ziel dieses Projektes war es die Wechselwirkung von Packung und Überdeckung zu untersuchen. Ein spezieller Fokus lag dabei auf der Kanten-zentrischen Variante von Packung und Überdeckung. Hier werden statt vollständig disjunkten Zielgraphen lediglich kantendisjunkte Zielgraphen gesucht – im Gegenzug muss jede Überdeckung aus Kanten bestehen. Dass die gewöhnliche und die Kantenversion der Packungs/Überdeckungs-Wechselwirkung grundverschieden sind, ist eine Haupterkenntnis des Projekts. (Es gab vorher Anzeichen für weitgehende Ähnlichkeiten.)

Projektbezogene Publikationen (Auswahl)

• Packing A-Paths of Length Zero Modulo Four
  H. Bruhn and A. Ulmer
  
• Erdös-Pósa property for labelled minors: 2-connected minors, SIAM Disc. Math.
  H. Bruhn, F. Joos and O. Schaudt
  
• Erdös-Pósa from Ball Packing. SIAM Disc. Math. 34 (2020), 1609–1619
  W. Cames van Batenburg, G. Joret, and A. Ulmer
  
• The edge-Erdös-Pósa property. Combinatorica (2020)
  M. Heinlein and F. Joos
  
• Zero A-paths and the Erdös-Pósa property
  A. Ulmer
  
• K4 -subdivisions have the edge-Erdös-Pósa property. SIAM Disc. Math. 35 (2021), 392–430
  H. Bruhn and M. Heinlein