Graph minors. XXI. Graphs with unique linkages

Neil Robertson, Paul Seymour

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

A linkage L in a graph G is a subgraph each component of which is a path, and it is vital if V (L) = V (G) and there is no other linkage in G joining the same pairs of vertices. We show that, if G has a vital linkage with p components, then G has tree-width bounded above by a function of p. This is the major step in the proof of the unproved lemma from Graph Minors XIII, and it has a number of other applications, including a constructive proof of the intertwining conjecture.

Original languageEnglish (US)
Pages (from-to)583-616
Number of pages34
JournalJournal of Combinatorial Theory. Series B
Volume99
Issue number3
DOIs
StatePublished - May 2009

All Science Journal Classification (ASJC) codes

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

Keywords

  • Disjoint paths
  • Graph minors
  • Intertwining conjecture
  • Tree-width

Fingerprint Dive into the research topics of 'Graph minors. XXI. Graphs with unique linkages'. Together they form a unique fingerprint.

Cite this