Packing and Covering Immersion Models of Planar subcubic Graphs

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 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370310
Contributor : Dimitrios M. Thilikos <>
Submitted on : Monday, January 22, 2018 - 9:06:53 AM
Last modification on : Thursday, November 15, 2018 - 3:36:21 PM

File

1602.04042 (1).pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Archontia Giannopoulou, O-Joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos. Packing and Covering Immersion Models of Planar subcubic Graphs. WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2016, Istanbul, Turkey. pp.74-84, ⟨10.1007/978-3-662-53536-3_7⟩. ⟨lirmm-01370310v2⟩

Share

Metrics

Record views

290

Files downloads

258