Delineating Half-Integrality of the Erd\Hos-P\'osa Property for Minors: the Case of Surfaces
<|reference_start|>Delineating Half-Integrality of the Erd\Hos-P\'osa Property for Minors: the Case of Surfaces: In 1986 Robertson and Seymour proved a generalization of the seminal result of Erd\H{o}s and P\'osa on the duality of packing and covering cycles: A graph has the Erd\H{o}s-P\'osa property for minors if and only if it is planar. In particular, for every non-planar graph $H$ they gave examples showing that the Erd\H{o}s-P\'osa property does not hold for $H.$ Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erd\H{o}s-P\'osa property for minors. Liu's proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known.   In this paper, we initiate the delineation of the half-integrality of the Erd\H{o}s-P\'osa property for minors. We conjecture that for every graph $H,$ there exists a unique (up to a suitable equivalence relation) graph parameter ${\textsf{EP}}_H$ such that $H$ has the Erd\H{o}s-P\'osa property in a minor-closed graph class $\mathcal{G}$ if and only if $\sup\{\textsf{EP}_H(G) \mid G\in\mathcal{G}\}$ is finite. We prove this conjecture for the class $\mathcal{H}$ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar $H\in\mathcal{H},$ the parameter ${\sf EP}_H(G)$ is precisely the maximum order of a Robertson-Seymour counterexample to the Erd\H{o}s-P\'osa property of $H$ which can be found as a minor in $G.$ Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in $\mathcal{H}.$<|reference_end|>
@article{paul2024delineating,
    title={Delineating Half-Integrality of the Erd\H{o}s-P\'osa Property for
  Minors: the Case of Surfaces},
    author={Christophe Paul and Evangelos Protopapas and Dimitrios M. Thilikos and
  Sebastian Wiederrecht},
    journal={arXiv preprint arXiv:2406.16647},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.16647},
    primaryClass={math.CO cs.DM}
}