<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue2" %>
Disjoint Paths in Graphs III, Characterization
Xingxing Yu
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
Annals of Combinatorics 7 (2) p.229-246 June, 2003
AMS Subject Classification: 05C38
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'}.
Keywords: disjoint paths, 3-planar graph, connectivity


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.