Disjoint Paths in Graphs I, 3-planar Graphs and Basic Obstructions

摘要

Let G be a graph, {a,b,c} (is contained in) V(G), and {a',b',c'} (is contained in) 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.