Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914847233409024 |
|---|---|
| author | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Wiederrecht, Sebastian |
| author_facet | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Wiederrecht, Sebastian |
| contents | In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa 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ős-Pósa property does not hold for $H.$ Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa 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ős-Pósa 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ős-Pósa 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ős-Pósa 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}.$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16647 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Wiederrecht, Sebastian Combinatorics Discrete Mathematics 05C83, 05C75, 05C10, 05C85, 68R10 G.2.2 In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa 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ős-Pósa property does not hold for $H.$ Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa 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ős-Pósa 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ős-Pósa 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ős-Pósa 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}.$ |
| title | Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces |
| topic | Combinatorics Discrete Mathematics 05C83, 05C75, 05C10, 05C85, 68R10 G.2.2 |
| url | https://arxiv.org/abs/2406.16647 |