Packing and covering immersion models of planar subcubic graphs

Archontia C. Giannopoulou, O. Joung Kwon, Jean Florent Raymond, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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: ℕ×ℕ → ℕ, 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.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Revised Selected Papers
EditorsPinar Heggernes
PublisherSpringer Verlag
Pages74-84
Number of pages11
ISBN (Print)9783662535356
DOIs
StatePublished - 2016
Event42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016 - Istanbul, Turkey
Duration: Jun 22 2016Jun 24 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9941 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016
Country/TerritoryTurkey
CityIstanbul
Period6/22/166/24/16

Keywords

  • Erdö–Pòsa properties
  • Graph immersions
  • Packings and coverings in graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Packing and covering immersion models of planar subcubic graphs'. Together they form a unique fingerprint.

Cite this