Loading...
Please wait, while we are loading the content...
Similar Documents
Normal Spanning Trees , Aronszajn Trees and Excluded Minors
| Content Provider | Semantic Scholar |
|---|---|
| Author | Diestel, Reinhard |
| Copyright Year | 2000 |
| Abstract | We prove 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 (א0,א1)-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 we deduce Halin’s further conjecture 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 (א0,א1)-regular bipartite graphs remains an open problem. One such class turns out to contain obvious infinite minor-antichains, so as an unexpected corollary we reobtain Thomas’s result that the infinite graphs are not well-quasi-ordered as minors. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.math.uni-hamburg.de/research/papers/hbm/hbm2000105.pdf |
| Alternate Webpage(s) | http://www.math.uni-hamburg.de/home/diestel/papers/Aronszajn.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Analog Aronszajn tree Connectivity (graph theory) Degeneracy (graph theory) Depth-first search Exclusion File spanning Graph - visual representation Obstruction Order (action) Search tree Spanning tree Theory Trees (plant) Tridiagonal matrix algorithm Trémaux tree |
| Content Type | Text |
| Resource Type | Article |
