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 -