Logo image
Sign in
Packing and covering immersion-expansions of planar sub-cubic graphs
Journal article   Open access   Peer reviewed

Packing and covering immersion-expansions of planar sub-cubic graphs

Archontia C. Giannopoulou, O-Joung Kwon, Jean-Florent Raymond and Dimitrios M. Thilikos
European Journal of Combinatorics, Vol.65, pp.154-167
2017

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.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image