Back to Search Start Over

ERDŐS-PÓSA PROPERTY FOR LABELED MINORS: 2-CONNECTED MINORS.

Authors :
BRUHN, HENNING
JOOS, FELIX
SCHAUDT, OLIVER
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]

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