Erdös-Pósa property for labeled minors: 2-connected minors - Bruhn, Henning; Joos, Felix; Schaudt, Oliver (SIAM journal on discrete mathematics, 2021)
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.
Gesehen am 09.09.2021