The almost bounded merge-width characterization conjecture
The almost bounded merge-width characterization conjecture
Let be a hereditary graph class. It has almost bounded merge-width if, for each fixed , every -vertex graph in has radius- merge-width at most ; analogously define almost bounded flip-width by replacing merge-width with flip-width. The class is monadically dependent if and only if it does not transduce the class of all graphs. Almost bounded merge-width characterization conjecture. The following conditions are equivalent:
For hereditary weakly sparse classes, the first two conditions are equivalent to nowhere denseness, and nowhere dense classes have almost bounded merge-width. The general hereditary characterization by monadic dependence remains open.
Sources & referencesView supporting material
Primary source
Jan Dreier and Szymon Toruńczyk, “Merge-width and First-Order Model Checking”, arXiv:2502.18065 (2026).
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.