Graph minors. XXI. Graphs with unique linkages

Neil Robertson; Paul Seymour

doi:10.1016/j.jctb.2008.08.003

Graph minors. XXI. Graphs with unique linkages

Neil Robertson, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

40 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 language	English (US)
Pages (from-to)	583-616
Number of pages	34
Journal	Journal of Combinatorial Theory. Series B
Volume	99
Issue number	3
DOIs	https://doi.org/10.1016/j.jctb.2008.08.003
State	Published - 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

Access to Document

10.1016/j.jctb.2008.08.003

Cite this

@article{2dd15c42e7b74a6f90edd27fbeb20ecd,

title = "Graph minors. XXI. Graphs with unique linkages",

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.",

keywords = "Disjoint paths, Graph minors, Intertwining conjecture, Tree-width",

author = "Neil Robertson and Paul Seymour",

note = "Funding Information: E-mail address: [email protected] (P. Seymour). 1 This research was supported by NSF grant DMS 8903132. 2 This work was carried out while the author was employed at Telcordia Technologies in Morristown, NJ.",

year = "2009",

month = may,

doi = "10.1016/j.jctb.2008.08.003",

language = "English (US)",

volume = "99",

pages = "583--616",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Graph minors. XXI. Graphs with unique linkages

AU - Robertson, Neil

AU - Seymour, Paul

N1 - Funding Information: E-mail address: [email protected] (P. Seymour). 1 This research was supported by NSF grant DMS 8903132. 2 This work was carried out while the author was employed at Telcordia Technologies in Morristown, NJ.

PY - 2009/5

Y1 - 2009/5

N2 - 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.

AB - 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.

KW - Disjoint paths

KW - Graph minors

KW - Intertwining conjecture

KW - Tree-width

UR - http://www.scopus.com/inward/record.url?scp=67649390838&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67649390838&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2008.08.003

DO - 10.1016/j.jctb.2008.08.003

M3 - Article

AN - SCOPUS:67649390838

SN - 0095-8956

VL - 99

SP - 583

EP - 616

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 3

ER -

Graph minors. XXI. Graphs with unique linkages

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this