Well-quasi-ordering conjecture for finite-tree-width graphs

Let a graph have finite tree-width if its tree-width is finite, and consider the minor relation on graphs. Finite-tree-width well-quasi-ordering conjecture. The graphs of finite tree-width are well-quasi-ordered under the minor relation. This is presented as an even stronger conjecture motivated by the fact that known counterexamples to well-quasi-ordering infinite graphs do not have finite tree-width. Its status is refuted according to the supplied evidence.

Sources & referencesView supporting material

Primary source

Sandra Albrechtsen, Raphael W. Jacobs, Paul Knappe and Max Pitz, “Linked tree-decompositions into finite parts”, arXiv:2405.06753 (2024).

Additional references

4 papers in this index state this conjecture (2013–2024). The statement above is taken from the most recent of them; the others are arXiv:2403.05862, arXiv:1611.03671, arXiv:1311.2160.

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.