Proof of Halin’s normal spanning tree conjecture. (English) Zbl 1487.05098
Summary: R. Halin [J. Graph Theory 35, No. 2, 128–151 (2000; Zbl 0960.05001)] conjectured 20 years ago that a graph has a normal spanning tree if and only if every minor of it has countable colouring number. We prove Halin’s conjecture. This implies a forbidden minor characterisation for the property of having a normal spanning tree.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C30 | Enumeration in graph theory |
| 05C05 | Trees |
| 05C83 | Graph minors |
Citations:
Zbl 0960.05001References:
| [1] | Bowler, N.; Carmesin, J.; Komjáth, P.; Reiher, C., The colouring number of infinite graphs, Combinatorica, 39, 1225-1235 (2019) · Zbl 1449.05189 · doi:10.1007/s00493-019-4045-9 |
| [2] | Brochet, J-M; Diestel, R., Normal tree orders for infinite graphs, Transactions of the American Mathematical Society, 345, 871-895 (1994) · Zbl 0814.05029 · doi:10.1090/S0002-9947-1994-1260198-4 |
| [3] | C. Bürger and J. Kurkofka, Duality theorems for stars and combs I: Arbitrary stars and combs, Journal of Graph Theory doi:10.1002/jgt.22757. |
| [4] | Diestel, R., Graph Theory (2017), Berlin: Springer, Berlin · Zbl 1375.05002 · doi:10.1007/978-3-662-53622-3 |
| [5] | R. Diestel, A simple existence criterion for normal spanning trees, The Electronic Journal of Combinatorics 23 (2016), Article no. 2.33. · Zbl 1336.05030 |
| [6] | Diestel, R.; Leader, I., Normal spanning trees, Aronszajn trees and excluded minors, Journal of the London Mathematical Society, 63, 16-32 (2001) · Zbl 1012.05051 · doi:10.1112/S0024610700001708 |
| [7] | Erde, J.; Gollin, P.; Joó, A.; Knappe, P.; Pitz, M., A Cantor-Bernstein-type theorem for spanning trees in infinite graphs, Journal of Combinatorial Theory. Series B, 149, 16-22 (2021) · Zbl 1466.05141 · doi:10.1016/j.jctb.2021.01.004 |
| [8] | Halin, R., Miscellaneous problems on infinite graphs, Journal of Graph Theory, 35, 128-151 (2000) · Zbl 0960.05001 · doi:10.1002/1097-0118(200010)35:2<128::AID-JGT6>3.0.CO;2-6 |
| [9] | Jung, H. A., Zusammenzüge und Unterteilungen von Graphen, Mathematische Nachrichten, 35, 241-267 (1967) · Zbl 0171.44803 · doi:10.1002/mana.19670350503 |
| [10] | Jung, H. A., Wurzelbäume und unendliche Wege in Graphen, Mathematische Nachrichten, 41, 1-22 (1969) · Zbl 0177.27001 · doi:10.1002/mana.19690410102 |
| [11] | Kunen, K., Set Theory (2011), London: College Publications, London · Zbl 1262.03001 |
| [12] | Pitz, M., A new obstruction for normal spanning trees, Bulletin of the London Mathematical Society, 53, 1220-1227 (2021) · Zbl 1475.05159 · doi:10.1112/blms.12495 |
| [13] | Pitz, M., A unified existence theorem for normal spanning trees, Journal of Combinatorial Theory. Series B, 145, 466-469 (2020) · Zbl 1448.05037 · doi:10.1016/j.jctb.2020.07.002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
