EXCLUDING A LONG DOUBLE PATH MINOR

The ''height'' of a graph G is defined to be the number of steps to co nstruct G by two simple graph operations. Let B-n be the graph obtaine d from an n-edge path by doubling each edge in parallel. Then, for any minor-closed class G of graphs, the following are proved to be equiva lent: (1) Some B-n is not in G; (2) There is a number h such that ever y graph in G has height at most h; (3) G is well-quasi-ordered by the topological minor relation; (4) There is a polynomial function p(.) su ch that the number of paths of every graph G in G is at most p(\V(G)\ + \E(G)\). (C) 1996 Academic Press, Inc.