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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
May 3, 2021
|
| In: |
SIAM journal on discrete mathematics
Year: 2021, Volume: 35, Issue: 2, Pages: 893-914 |
| ISSN: | 1095-7146 |
| DOI: | 10.1137/19M1289340 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1137/19M1289340 Verlag, lizenzpflichtig, Volltext: https://epubs.siam.org/doi/10.1137/19M1289340 
|
| Author Notes: | Henning Bruhn, Felix Joos, and Oliver Schaudt |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1769942548 | ||
| 003 | DE-627 | ||
| 005 | 20220820042239.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 210909s2021 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1137/19M1289340 |2 doi | |
| 035 | |a (DE-627)1769942548 | ||
| 035 | |a (DE-599)KXP1769942548 | ||
| 035 | |a (OCoLC)1341421037 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Bruhn, Henning |e VerfasserIn |0 (DE-588)1234066300 |0 (DE-627)1758740639 |4 aut | |
| 245 | 1 | 0 | |a Erdös-Pósa property for labeled minors |b 2-connected minors |c Henning Bruhn, Felix Joos, and Oliver Schaudt |
| 264 | 1 | |c May 3, 2021 | |
| 300 | |a 22 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 09.09.2021 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a 05C70 | |
| 650 | 4 | |a Erdös;Pósa | |
| 650 | 4 | |a minors | |
| 650 | 4 | |a packing | |
| 700 | 1 | |a Joos, Felix |d 1989- |e VerfasserIn |0 (DE-588)1075006171 |0 (DE-627)832846244 |0 (DE-576)442747438 |4 aut | |
| 700 | 1 | |a Schaudt, Oliver |d 1986- |e VerfasserIn |0 (DE-588)1017873925 |0 (DE-627)679795464 |0 (DE-576)354545434 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a Society for Industrial and Applied Mathematics |t SIAM journal on discrete mathematics |d Philadelphia, Pa. : Soc., 1988 |g 35(2021), 2, Seite 893-914 |h Online-Ressource |w (DE-627)26688539X |w (DE-600)1468404-4 |w (DE-576)078589975 |x 1095-7146 |7 nnas |
| 773 | 1 | 8 | |g volume:35 |g year:2021 |g number:2 |g pages:893-914 |g extent:22 |a Erdös-Pósa property for labeled minors 2-connected minors |
| 856 | 4 | 0 | |u https://doi.org/10.1137/19M1289340 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://epubs.siam.org/doi/10.1137/19M1289340 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20210909 | ||
| 993 | |a Article | ||
| 994 | |a 2021 | ||
| 998 | |g 1075006171 |a Joos, Felix |m 1075006171:Joos, Felix |d 110000 |d 110300 |e 110000PJ1075006171 |e 110300PJ1075006171 |k 0/110000/ |k 1/110000/110300/ |p 2 | ||
| 999 | |a KXP-PPN1769942548 |e 3976098264 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"type":{"bibl":"article-journal","media":"Online-Ressource"},"origin":[{"dateIssuedKey":"2021","dateIssuedDisp":"May 3, 2021"}],"language":["eng"],"title":[{"subtitle":"2-connected minors","title":"Erdös-Pósa property for labeled minors","title_sort":"Erdös-Pósa property for labeled minors"}],"note":["Gesehen am 09.09.2021"],"id":{"eki":["1769942548"],"doi":["10.1137/19M1289340"]},"recId":"1769942548","name":{"displayForm":["Henning Bruhn, Felix Joos, and Oliver Schaudt"]},"physDesc":[{"extent":"22 S."}],"person":[{"display":"Bruhn, Henning","given":"Henning","family":"Bruhn","role":"aut"},{"display":"Joos, Felix","given":"Felix","family":"Joos","role":"aut"},{"display":"Schaudt, Oliver","given":"Oliver","role":"aut","family":"Schaudt"}],"relHost":[{"title":[{"title":"SIAM journal on discrete mathematics","title_sort":"SIAM journal on discrete mathematics"}],"id":{"eki":["26688539X"],"issn":["1095-7146"],"zdb":["1468404-4"]},"disp":"Society for Industrial and Applied MathematicsSIAM journal on discrete mathematics","origin":[{"publisher":"Soc.","dateIssuedKey":"1988","dateIssuedDisp":"1988-","publisherPlace":"Philadelphia, Pa."}],"part":{"issue":"2","extent":"22","year":"2021","volume":"35","pages":"893-914","text":"35(2021), 2, Seite 893-914"},"language":["eng"],"corporate":[{"display":"Society for Industrial and Applied Mathematics","role":"aut"}],"titleAlt":[{"title":"Journal on discrete mathematics"}],"note":["Gesehen am 28.06.2021"],"recId":"26688539X","type":{"bibl":"periodical","media":"Online-Ressource"},"pubHistory":["1.1988 -"],"physDesc":[{"extent":"Online-Ressource"}],"name":{"displayForm":["Society for Industrial and Applied Mathematics"]}}]} | ||
| SRT | |a BRUHNHENNIERDOESPOSA3202 | ||