Graph minors. I. Excluding a forest |
| |
Authors: | Neil Robertson P.D. Seymour |
| |
Affiliation: | Department of Mathematics, Ohio State University, 231 W. 18th Ave, Columbus, Ohio 43210 USA |
| |
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?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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|