The tree-decomposition minor conjecture

Let GG be a connected graph, let TT be a tree, and let B\mathcal{B} be the bags of a tree decomposition (T,B)(T,\mathcal{B}) of GG. The width of this decomposition is the maximum, over all 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) denotes the minimum width of a tree decomposition of GG. A graph TT is a minor of GG if it can be obtained from GG by vertex and edge deletions and edge contractions.

The tree-decomposition minor 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 minor of GG.

The paper states that this conjecture is false, even for connected graphs of treewidth 22, and uses it as the first of three progressively stronger conjectures in the route to its main theorem.

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.