### Abstract

It has been conjectured by K. WAGNER that finite graphs are well-quasi-ordered by minor inclusion, i.e. being isomorphic to a contraction of a subgraph. A method is reported on here that shows promise of settling this conjecture. We have proved (1) that all graphs G not including a fixed planar graph H as a minor can be constructed by piecing together graphs on a bounded number of vertices in a tree-structure, and (2) by elaborating the KRUSKAL tree theorem that the class of graphs formed by piecing together graphs of bounded size in tree-structures is well-quasi-ordered. It follows from this that no infinite antichain of finite graphs can include even one planar graph and that there is a “good” algorithm for testing the presence of a fixed planar graph as a minor.

Original language | English (US) |
---|---|

Pages (from-to) | 343-354 |

Number of pages | 12 |

Journal | North-Holland Mathematics Studies |

Volume | 99 |

Issue number | C |

DOIs | |

State | Published - Jan 1 1984 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Some new results on the well-quasi-ordering of graphs'. Together they form a unique fingerprint.

## Cite this

*North-Holland Mathematics Studies*,

*99*(C), 343-354. https://doi.org/10.1016/S0304-0208(08)73830-1