Excluding a long double path minor
The `height' of a graph \(G\) is defined to be the number of steps to construct \(G\) by two simple graph operations. Let \(B_n\) be the graph obtained from an \(n\)-edge path by doubling each edge in parallel. Then, for any minor-closed class \({\mathcal G}\) of graphs, the following are proved to be equivalent: (1) Some \(B_n\) is not in \({\mathcal G}\). (2) There is a number \(h\) such that every graph in \({\mathcal G}\) has height at most \(h\). (3) \({\mathcal G}\) is well-quasi-orderd by the topological minor relation. (4) There is a polynomial function \(p(\cdot)\) such that the number of paths of every graph \(G\) in \({\mathcal G}\) is at most \(p(| V(G)|+ | E(G)|)\).
scientific article; zbMATH DE number 839131