The following is a summary of Linked tree-decompositions into finite parts [AJKP2024a] and Counterexamples regarding linked and lean tree-decompositions of infinite graphs [AJKP2024b] which are joint work with Sandra Albrechtsen, Raphael W. Jacobs and Max Pitz. In 2024 we submitted both of them. You can find their preprints on arXiv.
1.) Every graph of finite tree-width admits a rooted tree-decomposition into finite parts that is linked, tight, and componental [AJKP2024a, Theorem 1].
2.) Every graph G of finite tree-width admits a rooted tree-decomposition into finite parts that homeomorphically displays all the ends of G, their dominating vertices, and their combined degrees [AJKP2024a, Theorem 2].
3.) Every graph G without half-grid minor admits a lean tree-decomposition into finite parts [AJKP2024a, Theorem 3].
4.) There is a planar, locally finite, connected graph that admits no lean tree-decomposition [AJKP2024b, Example 1].
Robertson and Seymour’s work [RS90] on well-quasi-ordering finite graphs and also Thomas’s result [Tho89] on well-quasi-ordering (finite or infinite) graphs of tree-width < k heavily rely on Kříž and Thomas’s result [KT91]: Every (finite or infinite) graph of tree-width < k has a lean rooted tree-decomposition of width < k.
We depart from the question: Does Kříž and Thomas’s result generalise to graphs of finite tree-width, that is k = ℵ₀? Our 4th main result yields a witness G which negates the question because every locally finite graph has obviously finite tree-width. Moreover, as G additionally is planar, the clique K⁵ on five vertices is not a minor of G. All in all, Kříž and Thomas’s result does not even extend to graphs with no K⁵ minor. Yet, our 3rd main result generalises their result to graphs with no half-grid minor. This makes the missing gap in terms of excluded minors quite narrow. Based on our result, Albrechtsen [Alb2024] extended Robertson and Seymours tangle-tree duality theorem [RS91] to infinite graphs.
In light of the fact that the aforementioned applications of Kříž and Thomas’s result by Robertson and Seymour [RS90] and by Thomas [Tho89] himself only require the (rooted) tree-decomposition of width < k to be linked instead of lean, one may weaken the above question by demanding the desired tree-decomposition to be linked rather than lean. For trivial reasons, the answer now is in the positive, as every graph of finite tree-width admits a normal spanning tree by Jung's normal spanning tree criterion [Jun69] and the tree-decomposition given by the down-closures of any normal spanning tree is always linked. In turn we strengthened the answer with our 1st main result in such a way that it not only lies on the frontier of what is true but we also obtain unified, short proofs of the characterisations due to Robertson, Seymour and Thomas of graphs without half-grid minor [RST95], and of graphs without binary tree subdivision [ST93]. Additionally, a question of Halin [Hal77] is resolved by our 2nd main result obtained from our 1st main result.
[Alb2024] S. Albrechtsen, Tangle-tree duality in infinite graphs, preprint (2024). Available at arXiv:2405.06756.
[Hal77] R. Halin, Systeme disjunkter unendlicher Wege in Graphen, Numerische Methoden bei Optimierungsaufgaben Band 3: Optimierung bei graphentheoretischen und ganzzahligen Problemen (1977): 55–67.
[Jun69] H. A. Jung, Wurzelbäume und unendliche Wege in Graphen, Mathematische Nachrichten 41 (1969): 1–22.
[KT91] I. Kříž and R. Thomas, The menger-like property of the tree-width of infinite graphs, Journal of Combinatorial Theory, Series B 52.1 (1991): 86–91.
[RS90] N. Robertson and P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory, Series B 48 (1990): 227–254.
[RS91] N. Robertson and P. D. Seymour, Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory, Series B 52 (1991), 153–190.
[RST95] N. Robertson, P. D Seymour, and R. Thomas, Excluding infinite clique minors, Memoirs of the American Mathematical Society 118.566 (1995): vi+103.
[ST93] P. D Seymour and R. Thomas, Excluding infinite trees, Transactions of the American Mathematical Society 335.2 (1993): 597–630.
[Tho89] R. Thomas, Well-quasi-ordering infinite graphs with forbidden finite planar minor, Transactions of the American Mathematical Society 312.1 (1989): 279–313.