Variants of Merge-Width and Applications

Karolina Drabik, Maël Dumas, Colin Geniet, Jakub Nowakowski, Michał Pilipczuk, Szymon Toruńczyk

arXivarxiv/2602.23867Feb 27, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.23867
curl -X POST /api/v1/records/arxiv/2602.23867/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.23867/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'