Excluding a long double path minor (Q1907107)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Excluding a long double path minor |
scientific article |
Statements
Excluding a long double path minor (English)
0 references
29 September 1999
0 references
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)|)\).
0 references
minor-closed class
0 references
minor
0 references
number of paths
0 references