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.
Type de document :
Pré-publication, Document de travail
2018
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370310
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 22 janvier 2018 - 09:06:53
Dernière modification le : mardi 23 janvier 2018 - 01:22:25

Fichier

1602.04042 (1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01370310, version 2
  • ARXIV : 1602.04042

Collections

Citation

Archontia Giannopoulou, O-Joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos. Packing and Covering Immersion Models of Planar subcubic Graphs. 2018. 〈lirmm-01370310v2〉

Partager

Métriques

Consultations de la notice

67

Téléchargements de fichiers

30