### 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 language | English (US) |
---|---|

Pages (from-to) | 530-563 |

Number of pages | 34 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 102 |

Issue number | 2 |

DOIs | |

State | Published - 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

Robertson, N., & Seymour, P. (2012). Graph Minors. XXII. Irrelevant vertices in linkage problems.

*Journal of Combinatorial Theory. Series B*,*102*(2), 530-563. https://doi.org/10.1016/j.jctb.2007.12.007