Variants of Merge-Width and Applications
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911473715904512 |
|---|---|
| author | Drabik, Karolina Dumas, Maël Geniet, Colin Nowakowski, Jakub Pilipczuk, Michał Toruńczyk, Szymon |
| author_facet | Drabik, Karolina Dumas, Maël Geniet, Colin Nowakowski, Jakub Pilipczuk, Michał Toruńczyk, Szymon |
| contents | 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 terms of vertex orderings, and establish that graphs of bounded merge-width admit sparse quotients with bounded strong colouring numbers, are quasi-isometric to graphs of bounded expansion, and admit neighbourhood covers with constant overlap. We also discuss several other variants of merge-width and connections to adjacency labelling schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23867 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Variants of Merge-Width and Applications Drabik, Karolina Dumas, Maël Geniet, Colin Nowakowski, Jakub Pilipczuk, Michał Toruńczyk, Szymon Combinatorics Discrete Mathematics Data Structures and Algorithms 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 terms of vertex orderings, and establish that graphs of bounded merge-width admit sparse quotients with bounded strong colouring numbers, are quasi-isometric to graphs of bounded expansion, and admit neighbourhood covers with constant overlap. We also discuss several other variants of merge-width and connections to adjacency labelling schemes. |
| title | Variants of Merge-Width and Applications |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.23867 |