## Abstract

The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG_{1},...,G_{r} each of which has at mostk + 1 vertices, by identifying some vertices ofG_{i} pairwise with some ofG_{i+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