The strong spanning-tree decomposition conjecture
The strong spanning-tree decomposition conjecture
Let be a connected graph, let be a spanning tree of , and let be a tree decomposition of . For each vertex , define to be the subtree of induced by the vertices whose bags contain . The width is the maximum, over , of , and is the minimum width of a tree decomposition of .
The strong 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 and, for every vertex of , we have .
The condition requires each graph vertex to belong to the bag indexed by its corresponding vertex of the spanning tree. The supplied context says that the paper reduces this conjecture to a final conjecture and then disproves that final conjecture, but it does not explicitly state the independent status of this intermediate claim.
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.