ERDOES-POSA PROPERTY FOR LABELED MINORS: 2-CONNECTED MINORS

摘要

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.