The strong 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. For each vertex vV(G)v\in V(G), define TvT_v to be the subtree of TT induced by the vertices xx whose bags contain vv. The width is the maximum, over xV(T)x\in V(T), of {vV(G):xTv}1|\{v\in V(G):x\in T_v\}|-1, and tw(G)\operatorname{tw}(G) is the minimum width of a tree decomposition of GG.

The strong 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 and, for every vertex vv of GG, we have vTvv\in T_v.

The condition vTvv\in T_v 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

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.