{"id":"arxiv/2602.23867","url":"https://arxiv.org/abs/2602.23867","tags":["math.CO","cs.DM","cs.DS"],"score":0,"title":"Variants of Merge-Width and Applications","domain":"math.CO","source":"arxiv","authors":["Karolina Drabik","Maël Dumas","Colin Geniet","Jakub Nowakowski","Michał Pilipczuk","Szymon Toruńczyk"],"reviews":0,"subject":"math.CO","summary":"Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of several alternative definitions of merge-width, thus demonstrating the robustness of the notion. Our characterisation via definable merge-width uses vertex orderings inspired by generalised colouring numbers from sparsity theory, and enables us to obtain the first non-trivial approximation algorithm for merge-width, running in time $n^{O(1)} \\cdot 2^n$. We also obtain a new characterisation of bounded clique-width in…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-27","reactions":{}}