Georgia Institute of Technology College of Sciences

Let $\mathscr{G}$ and $\mathscr{H}$ be minor-closed graphs classes. The class $\mathscr{H}$ has the Erdős-Pósa property in $\mathscr{G}$ if there is a function $f : \mathbb{N} \to \mathbb{N}$ such that every graph $G$ in $\mathscr{G}$ either contains (a packing of) $k$ disjoint copies of some subgraph minimal graph $H \not\in \mathscr{H}$ or contains (a covering of) $f(k)$ vertices, whose removal creates a graph in $\mathscr{H}$. A class $\mathscr{G}$ is a minimal EP-counterexample for $\mathscr{H}$ if $\mathscr{H}$ does not have the Erdős-Pósa property in $\mathscr{G}$, however it does have this property for every minor-closed graph class that is properly contained in $\mathscr{G}$. The set $\mathfrak{C}_{\mathscr{H}}$ of the subset-minimal EP-counterexamples, for every $\mathscr{H}$, can be seen as a way to consider all possible Erdős-Pósa dualities that can be proven for minor-closed classes. We prove that, for every $\mathscr{H}$, $\mathfrak{C}_{\mathscr{H}}$ is finite and we give a complete characterization of it. In particular, we prove that $|\mathfrak{C}_{\mathscr{H}}| = 2^{\mathsf{poly}(\ell(h))}$, where $h$ is the maximum size of a minor-obstruction of $\mathscr{H}$ and $\ell(\cdot)$ is the unique linkage function. As a corollary of this, we obtain a constructive proof of Thomas' conjecture claiming that every minor-closed graph class has the half-integral Erdős-Pósa property in all graphs.

This is joint work with Christophe Paul, Dimitrios Thilikos, and Sebastian Wiederrecht.