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)|)\).
- Excluding a small minor
- Bounding the number of circuits of a graph
- Long induced paths in minor-closed graph classes and beyond
- Operations which preserve path-width at most two
- A wheels-and-whirls theorem for 3-connected 2-polymatroids
- On the structure of graphs with path-width at most two
- Recent progress on well-quasi-ordering graphs
- Excluding a large theta graph
- An overview of universal obstructions for graph parameters
- Minimal universal and dense minor closed classes
This page was built for publication: Excluding a long double path minor
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1907107)
