Abstract
The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG1,...,Gr each of which has at mostk + 1 vertices, by identifying some vertices ofGi pairwise with some ofGi+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width{approximately but not actually equal to}k. This, together with results of other papers, yields a "good" algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite.
Original language | English (US) |
---|---|
Pages (from-to) | 39-61 |
Number of pages | 23 |
Journal | Journal of Combinatorial Theory, Series B |
Volume | 35 |
Issue number | 1 |
DOIs | |
State | Published - Aug 1983 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics