The minimal-class conjecture for sparse hereditary graph classes
The minimal-class conjecture for sparse hereditary graph classes
Let be a sparse hereditary class of graphs with unbounded tree-width. A hereditary graph class is minimal of unbounded tree-width if it has unbounded tree-width, while every proper hereditary subclass has bounded tree-width. Minimal-class conjecture. The class does not contain a minimal class of unbounded tree-width. The preceding results establish this for hereditary classes of bounded vertex degree, classes with an excluded minor, and the path-star hereditary classes , and ; whether it holds for all sparse hereditary classes remains open.
Sources & referencesView supporting material
Primary source
Daniel Cocks, “t-sails and sparse hereditary classes of unbounded tree-width”, arXiv:2302.04783 (2024).
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.