Evangelos Protopapas, Erdős-Pósa Dualities for Minors

Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graphs classes. The class $\mathcal{H}$ has the Erdős-Pósa property in $\mathcal{G}$ if there is a function $f : \mathbb{N} \to \mathbb{N}$ such that every graph $G$ in $\mathcal{G}$ either contains (a packing of) $k$ disjoint copies of some subgraph minimal graph $H \not\in \mathcal{H}$ or contains (a covering of) $f(k)$ vertices, whose removal creates a graph in $\mathcal{H}$. A class $\mathcal{G}$ is a minimal EP-counterexample for $\mathcal{H}$ if $\mathcal{H}$ does not have the Erdős-Pósa property in $\mathcal{G}$, however it does have this property for every minor-closed graph class that is properly contained in $\mathcal{G}$. The set $\frak{C}_{\mathcal{H}}$ of the subset-minimal EP-counterexamples, for every $\mathcal{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 $\mathcal{H}$, $\frak{C}_{\mathcal{H}}$ is finite and we give a complete characterization of it. In particular, we prove that $|\frak{C}_{\mathcal{H}}| = 2^{\operatorname{poly}(\ell(h))}$, where $h$ is the maximum size of a minor-obstruction of $\mathcal{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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.