Packing and Covering Immersion Models of Planar subcubic Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2016

Packing and Covering Immersion Models of Planar subcubic Graphs

Résumé

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.
Fichier principal
Vignette du fichier
1602.04042 (1).pdf (549.87 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01370310 , version 1 (22-09-2016)
lirmm-01370310 , version 2 (22-01-2018)

Identifiants

Citer

Archontia C. Giannopoulou, O-Joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos. Packing and Covering Immersion Models of Planar subcubic Graphs. WG 2016 - 42nd International 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⟩
288 Consultations
291 Téléchargements

Altmetric

Partager

More