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

DOI10.1016/J.EJC.2017.05.009zbMATH Open1369.05046arXiv1602.04042OpenAlexW2681567936MaRDI QIDQ2400977FDOQ2400977

Authors: Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos 

Publication date: 31 August 2017

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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:BbbNimesBbbNightarrowBbbN$, 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 $GsetminusF$ does not contain $H$ as an immersion.

Full work available at URL: https://arxiv.org/abs/1602.04042

Recommendations

• Packing and covering immersion models of planar subcubic graphs
• Packing and covering immersions in 4-edge-connected graphs
• Induced immersions
• The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three

zbMATH Keywords

immersionconnected planar sub-cubic graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• On Independent Circuits Contained in a Graph
• An edge variant of the Erdős-Pósa property
• Strengthening Erdős -- Pósa property for minor-closed graph classes
• Polynomial bounds for the grid-minor theorem
• Large-treewidth graph decompositions and applications
• Drawing planar graphs using the canonical ordering
• Excluded grid theorem: improved and simplified
• Minors in graphs of large \(\theta_r\)-girth
• The structure of graphs not admitting a fixed immersion
• Title not available (Why is that?)
• Packing directed circuits
• Edge-disjoint odd cycles in planar graphs.
• The Erdős-Pósa property for clique minors in highly connected graphs
• The Erdös-Pósa property for matroid circuits
• On the presence of disjoint subgraphs of a specified type
• Tree-partitions of infinite graphs
• The Erdős-Pósa property for odd cycles in highly connected graphs
• The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
• On tree-partitions of graphs
• The Erdős-Pósa property for long circuits
• Algorithmic applications of tree-cut width
• Fixed-parameter tractability for subset feedback set problems with parity constraints

Cited In (8)

• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Erdős-Pósa property of chordless cycles and its applications
• Packing and covering immersion models of planar subcubic graphs
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Packing and covering immersions in 4-edge-connected graphs
• Covering and packing in graphs. V. Mispacking subcubes in hypercubes
• Erdős–Pósa property of obstructions to interval graphs
• Induced immersions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2400977)