- Series
- Graph Theory Seminar
- Time
- Tuesday, October 22, 2024 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Meike Hatzel – Institute for Basic Science (IBS) – https://meikehatzel.com/
- Organizer
- Evelyne Smith-Roberge
For a group Γ, a Γ-labelled graph is an undirected graph G where every orientation of an edge is assigned an element of Γ so that opposite orientations of the same edge are assigned inverse elements. A path in G is non-null if the product of the labels along the path is not the neutral element of Γ. We prove that for every finite group Γ, non-null S–T paths in Γ-labelled graphs exhibit the half- integral Erdős-Pósa property. More precisely, there is a function f , depending on Γ, such that for every Γ-labelled graph G, subsets of vertices S and T , and integer k, one of the following objects exists:
• a family F consisting of k non-null S–T paths in G such that every vertex of G participates in at most two paths of F; or
• a set X consisting of at most f (k) vertices that meets every non-null S–T path in G.
This in particular proves that in undirected graphs S–T paths of odd length have the half-integral Erdős-Pósa property.
This is joint work with Vera Chekan, Colin Geniet, Marek Sokołowski, Michał T. Seweryn, Michał Pilipczuk, and Marcin Witkowski.