<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue1" %>
Disjoint Paths in Graphs II, A Special Case
Xingxing Yu
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
Annals of Combinatorics 7 (1) p.105-126 March, 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 a special class of obstructions. This will be used to characterize all obstructions.
Keywords: disjoint paths, linkage, planar graph


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ĘC309.

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

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