The minimal-class conjecture for sparse hereditary graph classes

Let C\mathcal{C} 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 C\mathcal{C} 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 Rν\mathcal{R}^{\nu}, Rκ(q)\mathcal{R}^{\kappa(q)} and Rη\mathcal{R}^{\eta}; 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

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.