Logo image
Se connecter
Packing and Covering Immersion Models of Planar subcubic Graphs
Acte de colloque   Open Access

Packing and Covering Immersion Models of Planar subcubic Graphs

Archontia C. Giannopoulou, O-Joung Kwon, Jean-Florent Raymond et Dimitrios M. Thilikos
42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, Vol.9941, pp.74-84
LNCS
WG 2016 - 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (Istanbul, Turkey, 22/06/2016–24/06/2016)
26/09/2016

Résumé

Erdős–Pósa property Packings and coverings in graphs Graph immersions
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.

Fichiers et liens (1)

url
Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Logo image