### Abstract

Suppose that (s_{1}, t_{1}), ..., (s_{k}, t_{k}) are pairs of vertices of a graph. When can one choose a path between s_{i} and t_{i} for each i, all pairwise edge-disjoint? Menger's theorem answers this when s_{1}, ..., s_{k}, t_{1}, ..., t_{k} take only two distinct values, but the general problem is unsolved. We settle the two next simplest cases,. (i) when k = 2, and. (ii) when s_{1}, ..., s_{k}, t_{1}, ..., t_{k} take only three distinct values-the solution to this is obtained by applying a theorem of Mader. We obtain both good characterizations and good algorithms for these problems. The analogous "vertex-disjoint" problems are also solved.

Original language | English (US) |
---|---|

Pages (from-to) | 979-991 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 306 |

Issue number | 10-11 |

DOIs | |

State | Published - May 28 2006 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Disjoint paths in graphs'. Together they form a unique fingerprint.

## Cite this

Seymour, P. D. (2006). Disjoint paths in graphs.

*Discrete Mathematics*,*306*(10-11), 979-991. https://doi.org/10.1016/j.disc.2006.03.019