The tree-decomposition minor conjecture
Let be a connected graph, let be a tree, and let be the bags of a tree decomposition of . The width of this decomposition is the maximum, over all , of , and denotes the minimum width of a tree decomposition of . A graph is a minor of if it can be obtained from by vertex and edge deletions and edge contractions.
The tree-decomposition minor conjecture. There is a function such that every connected graph has a tree decomposition of width at most such that is a minor of .
The paper states that this conjecture is false, even for connected graphs of treewidth , and uses it as the first of three progressively stronger conjectures in the route to its main theorem.
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
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.