{"id":"arxiv/2611.06804","url":"https://arxiv.org/abs/2611.06804","tags":["cs.DM","cs.DS","cs.LO","math.CO","math.LO"],"score":0,"title":"Monadically Dependent Graph Classes Have Almost Bounded Merge-Width","domain":"cs.DM","source":"arxiv","authors":["Jan Dreier","Nikolas Mählmann","Michał Pilipczuk","Szymon Toruńczyk"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}