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

Packing and covering are two fundamental problems in many areas of mathematics. In graph theory, one of the oldest packing/covering problem concerns cycles: How many disjoint cycles can be found (packed) in a given graph? How many vertices need to be selected to meet (cover) every cycle in the graph? The classic Erdös-Pósa theorem asserts that these two numbers are related: the size of the cycle cover can be bounded by the size of a cycle packing. If that is the case, we say that the Erdös-Pósa property holds for the considered class of graphs (here: cycles). Cycles of even length, for instance, have the Erdös-Pósa property but odd cycles don't have it. That is, one may construct graphs that have only few disjoint odd cycles (in fact, at most one) but where arbitrarily many vertices are needed to cover every odd cycle.In the project, I want to study Erdös-Pósa properties. Three areas interest me in particular, namely labelled versions, edge-versions and the role of connectivity. The main aim is to find in each of these areas theorems that are as broad as possible, that contain existing results as special cases. In labelled versions, the graphs are additionally endowed with labels that need to be respected in the packing. This leads to far more powerful statements. In edge-versions of the Erdös-Pósa property, edge-disjoint objects are sought for rather than vertex-disjoint objects, as is the case in the ordinary setup. Asking for edge-disjoint objects makes as much sense but is less well studied. The third topic concerns graph classes (such as odd cycles) that fail to have the Erdös-Pósa property. Often, the Erdös-Pósa property is gained when the surrounding graph is (moderate) highly connected. For instance, it is known that edge-disjoint odd cycles gain the the Erdös-Pósa property when the surrounding graph is 4-connected. Is this a general phenomenon?

• DFG Programme: Research Grants