TY - GEN
T1 - Packing and covering immersion models of planar subcubic graphs
AU - Giannopoulou, Archontia C.
AU - Kwon, O. Joung
AU - Raymond, Jean Florent
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Springer-Verlag GmbH Germany 2016.
PY - 2016
Y1 - 2016
N2 - 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: ℕ×ℕ → ℕ, such that if H is a connected planar subcubic 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.
AB - 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: ℕ×ℕ → ℕ, such that if H is a connected planar subcubic 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.
KW - Erdö–Pòsa properties
KW - Graph immersions
KW - Packings and coverings in graphs
UR - http://www.scopus.com/inward/record.url?scp=84992718336&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84992718336&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-53536-3_7
DO - 10.1007/978-3-662-53536-3_7
M3 - Conference contribution
AN - SCOPUS:84992718336
SN - 9783662535356
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 74
EP - 84
BT - Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Revised Selected Papers
A2 - Heggernes, Pinar
PB - Springer Verlag
T2 - 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016
Y2 - 22 June 2016 through 24 June 2016
ER -