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 sugraph

G

after lifting incident edges. We prove that there is a polynomial function

f : B b b N i m e s B b b N i g h t a r r o w B b b 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 s e t m i n u s F

does not contain

H

as an immersion.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Packing and covering immersion-expansions of planar sub-cubic graphs