The spanning-tree decomposition conjecture
The spanning-tree decomposition conjecture
Let be a connected graph, let be a spanning tree of , and let be a tree decomposition of with width measured as the maximum bag size minus one. Write for the treewidth of .
The spanning-tree decomposition conjecture. There is a function such that every connected graph has a tree decomposition of width at most such that is a spanning tree of .
This is presented as a strengthening of the minor version and is one of three conjectures reduced successively to the next. The supplied text does not state its independent resolution, although the paper's overall strategy ultimately disproves the final, stronger conjecture.
Sources & referencesView supporting material
Primary source
Pablo Blanco, Linda Cook, Meike Hatzel, Claire Hilaire, Freddie Illingworth and Rose McCarty, “On tree decompositions whose trees are minors”, arXiv:2302.12106 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.