Skip to main content

Graph Minors. XXII. Irrelevant vertices in linkage problems

Author(s): Robertson, Neil; Seymour, Paul D.

To refer to this page use:
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. (C) 2011 Elsevier Inc. All rights reserved.
Publication Date: Mar-2012
Electronic Publication Date: 9-Aug-2011
Citation: Robertson, Neil, Seymour, Paul. (2012). Graph Minors. XXII. Irrelevant vertices in linkage problems. JOURNAL OF COMBINATORIAL THEORY SERIES B, 102 (530 - 563. doi:10.1016/j.jctb.2007.12.007
DOI: doi:10.1016/j.jctb.2007.12.007
ISSN: 0095-8956
Pages: 530 - 563
Type of Material: Journal Article
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.