The tree-decomposition minor conjecture
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.