Packing and covering immersion-expansions of planar sub-cubic graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles European Journal of Combinatorics Year : 2017

Packing and covering immersion-expansions of planar sub-cubic 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 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.
Fichier principal
Vignette du fichier
immep.pdf (360.39 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01610005 , version 1 (04-10-2017)
lirmm-01610005 , version 2 (12-06-2018)

Identifiers

Cite

Archontia C. Giannopoulou, O-Joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos. Packing and covering immersion-expansions of planar sub-cubic graphs. European Journal of Combinatorics, 2017, 65, pp.154-167. ⟨10.1016/j.ejc.2017.05.009⟩. ⟨lirmm-01610005v2⟩
282 View
279 Download

Altmetric

Share

Gmail Facebook X LinkedIn More