Dependent internal tree-ordering expansions and bounded twin-width

Let C\mathscr C be a hereditary weakly sparse class of graphs. An internal tree-ordering expansion of a graph is an expansion by the forest-ordering defined by a spanning forest; C\mathscr C has a dependent internal tree-ordering expansion when such expansions form a monadically dependent class. Internal tree-ordering conjecture. C\mathscr C has a dependent internal tree-ordering expansion if and only if C\mathscr C has bounded twin-width. This would characterize bounded twin-width for hereditary weakly sparse graph classes through dependent internal tree-orderings; the supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Hector Buffière, Yuquan Lin, Jaroslav Nešetřil, Patrice Ossona de Mendez and Sebastian Siebertz, “Characterizations of monadically dependent tree-ordered weakly sparse structures”, arXiv:2601.16039 (2026).

Additional references

2 papers in this index state this conjecture (2025–2026). The statement above is taken from the most recent of them; the others are arXiv:2505.00594.

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.