##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Seminar in Combinatorics

## Youngho Yoo

#### Texas A&M University (yyoo@tamu.edu)

## Erdős-Pósa property in group-labelled graphs

##### Abstract:

Erdős and Pósa proved in 1965 that every graph contains either $k$ vertex-disjoint cycles or a set of at most $O(k \log k)$ vertices intersecting every cycle. Such an approximate duality does not hold for odd cycles due to certain projective-planar grids, as pointed out by Lovász and Schrijver, and Reed showed in 1999 that these grids are the only obstructions to this duality. In this talk, we generalize these results by characterizing the obstructions in group-labelled graphs. Specializing to the group $\mathbb{Z}/m\mathbb{Z}$ gives a characterization of when cycles of length $\ell \bmod m$ satisfy this approximate duality, resolving a problem of Dejter and Neumann-Lara from 1988. We discuss other applications and analogous results for $A$-paths.

Based on joint work with Pascal Gollin, Kevin Hendrey, O-joung Kwon, and Sang-il Oum.

Lutz Warnke

### October 8, 2024

### 2:00 PM

AP&M 7321

Research Areas

Combinatorics****************************