Packing and covering immersion-expansions of planar sub-cubic graphs. (October 2017)

• Record Type: Journal Article
• Authors: Giannopoulou, Archontia C.; Kwon, O-joung; Raymond, Jean-Florent; Thilikos, Dimitrios M.
• Is Part Of: European journal of combinatorics. Volume 65(2017)
• Page Start: 154
• Page End: 167
• Publication Date: 2017-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.05.009
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 : N × N → 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 ∖ F does not contain H as an immersion.