The spanning-tree decomposition conjecture

Let GG be a connected graph, let TT be a spanning tree of GG, and let (T,B)(T,\mathcal{B}) be a tree decomposition of GG with width measured as the maximum bag size minus one. Write tw(G)\operatorname{tw}(G) for the treewidth of GG.

The spanning-tree decomposition conjecture. There is a function ff such that every connected graph GG has a tree decomposition (T,B)(T,\mathcal{B}) of width at most f(tw(G))f(\operatorname{tw}(G)) such that TT is a spanning tree of GG.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.