Graph Minors. XXII. Irrelevant vertices in linkage problems

Neil Robertson, Paul Seymour

Research output: Contribution to journalArticlepeer-review

36 Scopus citations


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
Issue number2
StatePublished - Mar 2012

All Science Journal Classification (ASJC) codes

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


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


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

Cite this