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...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) Kapitel/Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
28 Sep 2018
|
| In: |
Arxiv
Year: 2018, Pages: 1-22 |
| DOI: | 10.48550/arXiv.1809.11038 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.48550/arXiv.1809.11038 Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/1809.11038 
|
| Verfasserangaben: | Henning Bruhn, Matthias Heinlein, Felix Joos |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Gesehen am 27.07.2022 |
| Beschreibung: | Online Resource |
| DOI: | 10.48550/arXiv.1809.11038 |