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.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2017, 65, pp.154-167. 〈10.1016/j.ejc.2017.05.009〉
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-01610005
Contributeur : Jean-Florent Raymond <>
Soumis le : mercredi 4 octobre 2017 - 12:14:27
Dernière modification le : vendredi 16 mars 2018 - 20:26:02

Fichier

1-s2.0-S0195669817300677-main....
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

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, Elsevier, 2017, 65, pp.154-167. 〈10.1016/j.ejc.2017.05.009〉. 〈lirmm-01610005〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

25