{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T21:16:39Z","timestamp":1776374199082,"version":"3.51.2"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T00:00:00Z","timestamp":1651449600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T00:00:00Z","timestamp":1651449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Traditionally, the trees studied in infinite graphs are trees of height at most <jats:italic>\u03c9<\/jats:italic>, with each node adjacent to its parent and its children (and every branch of the tree inducing a path or a ray). However, there is also a method, systematically introduced by Brochet and Diestel, of turning arbitrary well-founded order trees <jats:italic>T<\/jats:italic> into graphs, in a way such that every <jats:italic>T<\/jats:italic>-branch induces a generalised path in the sense of Rado. This article contains an introduction to this method and then surveys four recent applications of order trees to infinite graphs, with relevance for well-quasi orderings, Hadwiger\u2019s conjecture, normal spanning trees and end-structure, the last two addressing long-standing open problems by Halin.<\/jats:p>","DOI":"10.1007\/s11083-022-09601-x","type":"journal-article","created":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T08:03:37Z","timestamp":1651478617000},"page":"65-81","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Applications of Order Trees in Infinite Graphs"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8961-6132","authenticated-orcid":false,"given":"Max","family":"Pitz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,2]]},"reference":[{"key":"9601_CR1","volume-title":"Results and Independence Proofs in Combinatorial Set Theory","author":"JE Baumgartner","year":"1970","unstructured":"Baumgartner, J.E.: Results and Independence Proofs in Combinatorial Set Theory. University of California, Berkeley (1970)"},{"key":"9601_CR2","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1007\/s00493-019-4045-9","volume":"39","author":"N Bowler","year":"2019","unstructured":"Bowler, N., Carmesin, J., Komj\u00e1th, P., Reiher, C.: The colouring number of infinite graphs. Combinatorica 39, 1225\u20131235 (2019)","journal-title":"Combinatorica"},{"key":"9601_CR3","doi-asserted-by":"publisher","first-page":"245","DOI":"10.4064\/fm337-10-2017","volume":"241","author":"N Bowler","year":"2018","unstructured":"Bowler, N., Geschke, G., Pitz, M.: Minimal obstructions for normal spanning trees. Fund. Math. 241, 245\u2013263 (2018)","journal-title":"Fund. Math."},{"issue":"2","key":"9601_CR4","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1090\/S0002-9947-1994-1260198-4","volume":"345","author":"J-M Brochet","year":"1994","unstructured":"Brochet, J.-M., Diestel, R.: Normal tree orders for infinite graphs. Trans. Am. Math. Soc. 345(2), 871\u2013895 (1994)","journal-title":"Trans. Am. Math. Soc."},{"key":"9601_CR5","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s11856-020-2030-z","volume":"238","author":"C B\u00fcrger","year":"2020","unstructured":"B\u00fcrger, C., Pitz, M.: Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths. Israel J. Math. 238, 479\u2013500 (2020)","journal-title":"Israel J. Math."},{"key":"9601_CR6","volume-title":"Graph Theory","author":"R Diestel","year":"2015","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer, Berlin (2015)","edition":"5th edn"},{"issue":"1","key":"9601_CR7","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1112\/S0024610700001708","volume":"63","author":"R Diestel","year":"2001","unstructured":"Diestel, R., Leader, I.: Normal spanning trees, Aronszajn trees and excluded minors. J. Lond. Math. Soc. 63(1), 16\u201332 (2001)","journal-title":"J. Lond. Math. Soc."},{"issue":"8","key":"9601_CR8","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1016\/j.disc.2016.09.028","volume":"340","author":"M Elekes","year":"2017","unstructured":"Elekes, M., Soukup, D. T., Soukup, L., Szentmikl\u00f3ssy, Z.: Decompositions of edge-colored infinite complete graphs into monochromatic paths. Discret. Math. 340(8), 2053\u20132069 (2017)","journal-title":"Discret. Math."},{"key":"9601_CR9","doi-asserted-by":"crossref","unstructured":"Geschke, S., Kurkofka, J., Melcher, R., Pitz, M.: Halin\u2019s end degree conjecture. Israel J. Math. (2021)","DOI":"10.1007\/978-3-030-83823-2_13"},{"issue":"2","key":"9601_CR10","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF02579376","volume":"5","author":"A Hajnal","year":"1985","unstructured":"Hajnal, A.: The chromatic number of the product of two \u21351-chromatic graphs can be countable. Combinatorica 5(2), 137\u2013139 (1985)","journal-title":"Combinatorica"},{"issue":"1-2","key":"9601_CR11","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1002\/mana.19650300106","volume":"30","author":"R Halin","year":"1965","unstructured":"Halin, R.: \u00dcber die Maximalzahl fremder unendlicher Wege in Graphen. Mathematische Nachrichten 30(1\u20132), 63\u201385 (1965)","journal-title":"Mathematische Nachrichten"},{"key":"9601_CR12","doi-asserted-by":"crossref","unstructured":"Halin, R.: Unterteilungen vollst\u00e4ndiger Graphen in Graphen mit unendlicher chromatischer zahl. In: Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg, vol. 31, pp. 156\u2013165. Springer (1967)","DOI":"10.1007\/BF02992395"},{"key":"9601_CR13","doi-asserted-by":"crossref","unstructured":"Halin, R.: Simplicial decompositions of infinite graphs. In: Annals of Discrete Mathematics, vol. 3, pp. 93\u2013109. Elsevier (1978)","DOI":"10.1016\/S0167-5060(08)70500-4"},{"issue":"2","key":"9601_CR14","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1002\/1097-0118(200010)35:2<128::AID-JGT6>3.0.CO;2-6","volume":"35","author":"R Halin","year":"2000","unstructured":"Halin, R.: Miscellaneous problems on infinite graphs. J. Graph Theory 35(2), 128\u2013151 (2000)","journal-title":"J. Graph Theory"},{"key":"9601_CR15","unstructured":"Jech, T.: Set theory, The Third Millennium Edition Springer Monographs in Mathematics (2013)"},{"key":"9601_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/mana.19690410102","volume":"41","author":"H Jung","year":"1969","unstructured":"Jung, H.: Wurzelb\u00e4ume und unendliche Wege in Graphen. Math. Nachr. 41, 1\u201322 (1969)","journal-title":"Math. Nachr."},{"issue":"5-6","key":"9601_CR17","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1002\/mana.19670350503","volume":"35","author":"HA Jung","year":"1967","unstructured":"Jung, H.A.: Zusammenz\u00fcge und Unterteilungen von Graphen. Mathematische Nachrichten 35(5-6), 241\u2013267 (1967)","journal-title":"Mathematische Nachrichten"},{"key":"9601_CR18","doi-asserted-by":"crossref","unstructured":"Komj\u00e1th, P.: A note on minors of uncountable graphs. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 117, pp 7\u20139 (1995)","DOI":"10.1017\/S0305004100072881"},{"key":"9601_CR19","doi-asserted-by":"crossref","unstructured":"Komj\u00e1th, P.: Hadwiger\u2019s conjecture for uncountable graphs. In: Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg, vol. 87, pp. 337\u2013341. Springer (2017)","DOI":"10.1007\/s12188-016-0170-1"},{"issue":"2","key":"9601_CR20","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0012-365X(90)90150-G","volume":"81","author":"I Kriz","year":"1990","unstructured":"Kriz, I., Thomas, R.: Clique-sums, tree-decompositions and compactness. Discrete Math. 81(2), 177\u2013185 (1990)","journal-title":"Discrete Math."},{"key":"9601_CR21","doi-asserted-by":"publisher","first-page":"107176","DOI":"10.1016\/j.aim.2020.107176","volume":"369","author":"C Lambie-Hanson","year":"2020","unstructured":"Lambie-Hanson, C.: On the growth rate of chromatic numbers of finite subgraphs. Adv. Math. 369, 107176 (2020)","journal-title":"Adv. Math."},{"key":"9601_CR22","doi-asserted-by":"crossref","unstructured":"Nash-Williams, C.S.J.: On well-quasi-ordering infinite trees. In: Mathematical proceedings of the cambridge philosophical society, vol. 61, pp 697\u2013720. Cambridge University Press (1965)","DOI":"10.1017\/S0305004100039062"},{"key":"9601_CR23","doi-asserted-by":"crossref","unstructured":"Pitz, M.: A new obstruction for normal spanning trees. Bull. London Math. Soc. 53, 1220\u20131227\u00a0(2021)","DOI":"10.1112\/blms.12495"},{"key":"9601_CR24","unstructured":"Pitz, M.: A note on minor antichains of uncountable graphs. arXiv:2005.05816 (2020)"},{"key":"9601_CR25","doi-asserted-by":"crossref","unstructured":"Pitz, M.: Quickly proving Diestel\u2019s normal spanning tree criterion. Electron. J. Comb. 28(3), P3.59 (2021)","DOI":"10.37236\/9619"},{"key":"9601_CR26","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/j.jctb.2020.07.002","volume":"145","author":"M Pitz","year":"2020","unstructured":"Pitz, M.: A unified existence theorem for normal spanning trees. J. Comb. Theory Series B 145, 466\u2013469 (2020)","journal-title":"J. Comb. Theory Series B"},{"key":"9601_CR27","doi-asserted-by":"crossref","unstructured":"Pitz, M.: Proof of Halin\u2019s normal spanning tree conjecture. Israel J. Math. 246, 353\u2013370 (2021)","DOI":"10.1007\/s11856-021-2249-3"},{"key":"9601_CR28","doi-asserted-by":"crossref","unstructured":"Rado, R.: Monochromatic paths in graphs. In: Annals of discrete mathematics, vol. 3, pp. 191\u2013194. Elsevier (1978)","DOI":"10.1016\/S0167-5060(08)70507-7"},{"issue":"1-3","key":"9601_CR29","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0012-365X(91)90343-Z","volume":"95","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Excluding infinite minors. Discret. Math. 95(1-3), 303\u2013319 (1991)","journal-title":"Discret. Math."},{"key":"9601_CR30","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jctb.2015.05.004","volume":"115","author":"DT Soukup","year":"2015","unstructured":"Soukup, D.T.: Trees, Ladders and graphs. J. Comb. Theory, Series B 115, 96\u2013116 (2015)","journal-title":"J. Comb. Theory, Series B"},{"issue":"1","key":"9601_CR31","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s11856-017-1552-5","volume":"221","author":"DT Soukup","year":"2017","unstructured":"Soukup, D.T.: Decompositions of edge-coloured infinite complete graphs into monochromatic paths II. Israel J. Math. 221(1), 235\u2013273 (2017)","journal-title":"Israel J. Math."},{"issue":"4","key":"9601_CR32","doi-asserted-by":"publisher","first-page":"655","DOI":"10.2307\/2373113","volume":"85","author":"AH Stone","year":"1963","unstructured":"Stone, A.H.: On \u03c3-discreteness and Borel isomorphism. Am. J. Math. 85(4), 655\u2013666 (1963)","journal-title":"Am. J. Math."},{"issue":"3","key":"9601_CR33","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0016-660X(72)90010-4","volume":"2","author":"AH Stone","year":"1972","unstructured":"Stone, A.H.: Non-separable Borel sets, II. Gen. Topol. Appl. 2(3), 249\u2013270 (1972)","journal-title":"Gen. Topol. Appl."},{"key":"9601_CR34","doi-asserted-by":"crossref","unstructured":"Thomas, R.: A counter-example to Wagner\u2019s conjecture for infinite graphs. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 103, pp. 55\u201357. Cambridge University Press (1988)","DOI":"10.1017\/S0305004100064616"},{"key":"9601_CR35","doi-asserted-by":"crossref","unstructured":"Todorcevic, S.: On a conjecture of R. Rado. J. London Math. Soc.(2) 27(1), 1\u20138 (1983)","DOI":"10.1112\/jlms\/s2-27.1.1"}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-022-09601-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11083-022-09601-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-022-09601-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T02:43:05Z","timestamp":1714099385000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11083-022-09601-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,2]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9601"],"URL":"https:\/\/doi.org\/10.1007\/s11083-022-09601-x","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"value":"0167-8094","type":"print"},{"value":"1572-9273","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,2]]},"assertion":[{"value":"7 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}