Erdös-Pósa property for labeled minors: 2-connected minors
In the 1960s, Erdös and Pósa proved that there is a packing-covering duality for cycles in graphs. As part of the graph minor project, Robertson and Seymour greatly extended this: there is such a duality for $H$-expansions in graphs if and only if $H$ is a planar graph (this includes the previous...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
May 3, 2021
|
| In: |
SIAM journal on discrete mathematics
Year: 2021, Jahrgang: 35, Heft: 2, Pages: 893-914 |
| ISSN: | 1095-7146 |
| DOI: | 10.1137/19M1289340 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1137/19M1289340 Verlag, lizenzpflichtig, Volltext: https://epubs.siam.org/doi/10.1137/19M1289340 
|
| Verfasserangaben: | Henning Bruhn, Felix Joos, and Oliver Schaudt |
| Zusammenfassung: | In the 1960s, Erdös and Pósa proved that there is a packing-covering duality for cycles in graphs. As part of the graph minor project, Robertson and Seymour greatly extended this: there is such a duality for $H$-expansions in graphs if and only if $H$ is a planar graph (this includes the previous result for $H=K_3$). We consider vertex labeled graphs and minors and provide such a characterization for 2-connected labeled graphs $H$. In particular, this generalizes results of Kakimura, Kawarabayashi and Marx [J. Combin. Theory Ser. B, 101 (2011), pp. 378--381] and Huynh, Joos, and Wollan [Combinatorica, 39 (2019), pp. 91--133] up to weaker dependencies of the parameters. |
|---|---|
| Beschreibung: | Gesehen am 09.09.2021 |
| Beschreibung: | Online Resource |
| ISSN: | 1095-7146 |
| DOI: | 10.1137/19M1289340 |