Paper Info
Title
Erdos-Posa Property For Labeled Minors: 2-Connected Minors
Abstract
In the 1960s, Erdos 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.
Year
DOI
Venue
2021
10.1137/19M1289340
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
Erdos-Posa, minors, packing
Journal
35
Issue
ISSN
Citations 
2
0895-4801
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
henning bruhn117724.93
Felix Joos23711.20
Oliver Schaudt39521.74