The Erdo{double acute}s-Pósa property for clique minors in highly connected graphs

Link:
Autor/in:
Erscheinungsjahr:
2012
Medientyp:
Text
Schlagworte:
  • Algorithms
  • Polynomials
  • Feedback vertex
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Algorithms
  • Polynomials
  • Feedback vertex
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • We prove the existence of a function f:N-2 -> N such that, for all p, k is an element of N, every (k(p - 3) + 14p + 14)-connected graph either has k disjoint K-p-minors or contains a set of at most f(p, k) vertices whose deletion kills all its K-p-minors. For fixed p >= 5, the connectivity bound of about k(p - 3) is smallest possible, up to an additive constant: if we assume less connectivity in terms of k, there will be no such function f. (C) 2011 Published by Elsevier Inc.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/85a4b0c6-cd93-4e3a-8626-1b894cf758ca