Disjoint Paths in Graphs III, Characterization

Xingxing Yu

School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA

yu@math.gatech.edu

Annals of Combinatorics 7 (2) p.229-246 June, 2003

Abstract:

Let G be a graph,
{a, b, c} V(G), and {a', b', c'}
V(G) such that {a, b, c}{a', b', c'}.
We say that (G, {a, c}, {a', c'}, (b, b')) is an *obstruction* if, for
any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path
is from b to b'. In this paper we characterize obstructions. As a consequence,
we show that no obstruction can be 8-connected, unless b=b' or {a, c}={a', c'}.

References:

1. K. Chakravarti and N. Robertson, Covering three edges with a bond in a nonseparable graph, In: Annals of Discrete Math., Deza and Rosenberg Eds., 1979, p. 247.

2. P.D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980) 293--309.

3. C. Thomassen, 2-Linked graphs, Europ. J. Combin. 1 (1980) 371--378.

4. X. Yu, Subdivisions in planar graphs, J. Combin. Theory, Ser. B 72 (1998) 10--52.

5. X. Yu, Disjoint paths in graphs I, 3-planar graphs and basic obstructions, Ann. Combin. 7 (2003) 89--103.

6. X. Yu, Disjoint paths in graphs II, a special case, Ann. Combin. 7 (2003) 105--126.