Back to Search
Start Over
ERDŐS-PÓSA PROPERTY FOR LABELED MINORS: 2-CONNECTED MINORS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2021, Vol. 35 Issue 2, p893-914. 12p. - Publication Year :
- 2021
-
Abstract
- In the 1960s, Erd Hos and Posa 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 = K3). 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MINORS
*GRAPH labelings
*PLANAR graphs
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 35
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 154646068
- Full Text :
- https://doi.org/10.1137/19M1289340