The strong spanning-tree decomposition conjecture

About 3 years old · traced to

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 v∈V(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 x∈V(T)x\in V(T), of ∣{v∈V(G):x∈Tv}∣−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 v∈Tvv\in T_v.

The condition v∈Tvv\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.

References

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.