<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue1" %>
Disjoint Paths in Graphs I, 3-planar Graphs and Basic Obstructions
Xingxing Yu
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA
Annals of Combinatorics 7 (1) p.89-103 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'. Robertson and Seymour asked the problem of characterizing all obstructions. In this paper, we present a list of ``basic'' obstructions and show how to produce other obstructions from these basic ones. We also prove results about disjoint paths in graphs. Results in this paper will be used in subsequent papers 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.A. Catlin, Haj車s' graph-coloring conjecture: variations and counterexamples, J. Combin. Theory, Ser. B 26 (2) (1979) 268每274.

3. G.A. Dirac, Homomorphism theorems for graphs, Math. Ann. 153 (1964) 69每80.

4. T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995.

5. A.E. K谷zdy and P. J. McGuinness, Do 3n-5 edges suffice for subdivision of K5, J. Graph Theory 15 (1991) 289每406.

6. W. Mader, 3n-5 edges do force a subdivision of K5, Combinatorica 18 (4) (1998) 569每595.

7. N. Robertson and P.D. Seymour, Private communication with R. Thomas.

8. P. D. Seymour, Private communication.

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

10. C. Thomassen, 2-linked graphs, Europ. J. Combin. 1 (1980) 371每378.

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