The edge-Erdős-Pósa property
Robertson and Seymour proved that the family of all graphs containing a fixed graph $H$ as a minor has the Erd\H{o}s-P\'osa property if and only if $H$ is planar. We show that this is no longer true for the edge version of the Erd\H{o}s-P\'osa property, and indeed even fails when $H$ is an...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) Chapter/Article |
| Language: | English |
| Published: |
28 Sep 2018
|
| In: |
Arxiv
Year: 2018, Pages: 1-22 |
| DOI: | 10.48550/arXiv.1809.11038 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.48550/arXiv.1809.11038 Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/1809.11038 
|
| Author Notes: | Henning Bruhn, Matthias Heinlein, Felix Joos |
| Summary: | Robertson and Seymour proved that the family of all graphs containing a fixed graph $H$ as a minor has the Erd\H{o}s-P\'osa property if and only if $H$ is planar. We show that this is no longer true for the edge version of the Erd\H{o}s-P\'osa property, and indeed even fails when $H$ is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos. |
|---|---|
| Item Description: | Gesehen am 27.07.2022 |
| Physical Description: | Online Resource |
| DOI: | 10.48550/arXiv.1809.11038 |