Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777407 | European Journal of Combinatorics | 2017 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos,