×

Packing and covering immersion-expansions of planar sub-cubic graphs. (English) Zbl 1369.05046

Summary: A graph \(H\) is an immersion of a graph \(G\) if \(H\) can be obtained by some subgraph \(G\) after lifting incident edges. We prove that there is a polynomial function \(f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\), such that if \(H\) is a connected planar sub-cubic graph on \(h > 0\) edges, \(G\) is a graph, and \(k\) is a non-negative integer, then either \(G\) contains \(k\) vertex/edge-disjoint subgraphs, each containing \(H\) as an immersion, or \(G\) contains a set \(F\) of \(f(k,h)\) vertices/edges such that \(G \setminus F\) does not contain \(H\) as an immersion.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[2] Birmelé, Etienne; Bondy, Joh Adrian; Reed, Bruce A., The Erdös-Pósa property for long circuits, Combinatorica, 27, 2, 135-145 (2007) · Zbl 1136.05028
[3] Chatzidimitriou, D.; Raymond, J.-F.; Sau, I.; Thilikos, D. M., Minors in graphs of large \(\theta_r\)-girth, European J. Combin., 65, 106-121 (2017) · Zbl 1369.05187
[8] Diestel, Reinhard, (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2005), Springer-Verlag: Springer-Verlag Heidelberg) · Zbl 1074.05001
[9] Diestel, Reinhard; Kawarabayashi, Ken-Ichi; Wollan, Paul, The Erdős-Pósa property for clique minors in highly connected graphs, J. Combin. Theory Ser. B, 102, 2, 454-469 (2012) · Zbl 1239.05172
[10] Ding, Guoli; Oporowski, Bogdan, On tree-partitions of graphs, Discrete Math., 149, 1-3, 45-58 (1996) · Zbl 0844.05078
[11] Erdős, Paul; Pósa, Louis, On independent circuits contained in a graph, Canad. J. Math., 17, 347-352 (1965) · Zbl 0129.39904
[12] Fomin, Fedor V.; Saurabh, Saket; Thilikos, Dimitrios M., Strengthening erdős-Pósa property for minor-closed graph classes, J. Graph Theory, 66, 3, 235-240 (2011) · Zbl 1216.05148
[13] Ganian, Robert; Kim, Eun Jung; Szeider, Stefan, Algorithmic applications of tree-cut width, (Italiano, Giuseppe F.; Pighizzini, Giovanni; Sannella, Donald T., Mathematical Foundations of Computer Science 2015. Mathematical Foundations of Computer Science 2015, Lecture Notes in Computer Science, vol. 9235 (2015), Springer: Springer Berlin, Heidelberg), 8-360 · Zbl 1465.68211
[14] Geelen, Jim; Kabell, Kasper, The Erdős-Pósa property for matroid circuits, J. Combin. Theory Ser. B, 99, 2, 407-419 (2009) · Zbl 1229.05071
[15] Halin, Rudolf, Tree-partitions of infinite graphs, Discrete Math., 97, 1-3, 203-217 (1991) · Zbl 0763.05027
[16] Kakimura, Naonori; Kawarabayashi, Ken-ichi, Fixed-parameter tractability for subset feedback set problems with parity constraints, Theoret. Comput. Sci., 576, 61-76 (2015) · Zbl 1312.68104
[17] Kant, Goos, Drawing planar graphs using the canonical ordering, Algorithmica, 16, 1, 4-32 (1996) · Zbl 0851.68086
[18] Kawarabayashi, Ken-Ichi; Nakamoto, Atsuhiro, The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces, Discrete Math., 307, 6, 764-768 (2007) · Zbl 1112.05056
[19] Král’, Daniel; Voss, Heinz-Jürgen, Edge-disjoint odd cycles in planar graphs, J. Combin. Theory Ser. B, 90, 1, 107-120 (2004) · Zbl 1033.05064
[21] Rautenbach, Dieter; Reed, Bruce A., The Erdos-Pósa property for odd cycles in highly connected graphs, Combinatorica, 21, 2, 267-278 (2001) · Zbl 0981.05066
[22] Raymond, Jean-Florent; Sau, Ignasi; Thilikos, Dimitrios M., An edge variant of the Erdős-Pósa property, Discrete Appl. Math. (2017), in press · Zbl 1336.05108
[23] Reed, Bruce A.; Robertson, Neil; Seymour, Paul D.; Thomas, Robin, Packing directed circuits, Combinatorica, 16, 4, 535-554 (1996) · Zbl 0881.05050
[24] Robertson, Neil; Seymour, Paul D., Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41, 2, 92-114 (1986) · Zbl 0598.05055
[25] Robertson, Neil; Seymour, Paul D.; Thomas, Robin, Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62, 2, 323-348 (1994) · Zbl 0807.05023
[26] Seese, Detlef, Tree-partite graphs and the complexity of algorithms, (Proceedings of Fundamentals of Computation Theory. Proceedings of Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 199 (1985), Springer: Springer Berlin, Heidelberg), 412-421 · Zbl 0574.68036
[27] Thomassen, Carsten, On the presence of disjoint subgraphs of a specified type, J. Graph Theory, 12, 1, 101-111 (1988) · Zbl 0662.05032
[28] Wollan, Paul, The structure of graphs not admitting a fixed immersion, J. Combin. Theory Ser. B, 110, 47-66 (2015) · Zbl 1302.05148
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.