Graph Minors. XXII. Irrelevant vertices in linkage problems

Neil Robertson, Paul Seymour

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

In the algorithm for the disjoint paths problem given in Graph Minors XIII, we used without proof a lemma that, in solving such a problem, a vertex which was sufficiently "insulated" from the rest of the graph by a large planar piece of the graph was irrelevant, and could be deleted without changing the problem. In this paper we prove the lemma.

Original languageEnglish (US)
Pages (from-to)530-563
Number of pages34
JournalJournal of Combinatorial Theory. Series B
Volume102
Issue number2
DOIs
StatePublished - Mar 1 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Disjoint paths algorithm
  • Graph minors
  • Irrelevant vertex
  • Linkage problem

Fingerprint Dive into the research topics of 'Graph Minors. XXII. Irrelevant vertices in linkage problems'. Together they form a unique fingerprint.

  • Cite this