Back to Search
Start Over
NORMAL SPANNING TREES, ARONSZAJN TREES AND EXCLUDED MINORS.
- Source :
-
Journal of the London Mathematical Society . 02/01/2001, Vol. 63 Issue 1, p16-32. 17p. - Publication Year :
- 2001
-
Abstract
- It is proved that a connected infinite graph has a normal spanning tree (the infinite analogue of a depth-first search tree) if and only if it has no minor obtained canonically from either an (50, 51)-regular bipartite graph or an order-theoretic Aronszajn tree. This disproves Halin's conjecture that only the first of these obstructions was needed to characterize the graphs with normal spanning trees. As a corollary Halin's further conjecture is deduced, that a connected graph has a normal spanning tree if and only if all its minors have countable colouring number.The precise classification of the (50, 51)-regular bipartite graphs remains an open problem. One such class turns out to contain obvious infinite minor-antichains, so as an unexpected corollary Thomas's result that the infinite graphs are not well-quasi-ordered as minors is reobtained. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00246107
- Volume :
- 63
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of the London Mathematical Society
- Publication Type :
- Academic Journal
- Accession number :
- 57134060
- Full Text :
- https://doi.org/10.1112/S0024610700001708