Paperlane

no. 9 · Thursday 5 November 2026

Monadically Dependent Graph Classes Have Almost Bounded Merge-Width

Jan Dreier, Nikolas Mählmann, Michał Pilipczuk and Szymon Toruńczyk

math.CO · via cs.DM

Abstract

A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions in the form of merge sequences can be computed in nearly-cubic time. This is a step towards the proof of fixed-parameter tractability of model checking first-order logic on monadically dependent graph classes, which is achieved in a companion paper.

fields
Combinatorics, Logic
pdf ↗ page arXiv:2611.06804 ↗