Portal de Periódicos da CAPES

Disjoint paths in graphs

2006; Elsevier BV; Volume: 306; Issue: 10-11 Linguagem: Inglês

10.1016/j.disc.2006.03.019

1872-681X

Paul Seymour,

Graph Labeling and Dimension Problems

Suppose that (s1,t1),…,(sk,tk) are pairs of vertices of a graph. When can one choose a path between si and ti for each i, all pairwise edge-disjoint? Menger's theorem answers this when s1,…,sk,t1,…,tk 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 s1,…,sk,t1,…,tk 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.