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
- General Mathematics