$χ$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909649744166912 |
|---|---|
| author | Bonamy, Marthe Geniet, Colin |
| author_facet | Bonamy, Marthe Geniet, Colin |
| contents | Merge-width, recently introduced by Dreier and Toruńczyk, is a common generalisation of bounded expansion classes and twin-width for which the first-order model checking problem remains tractable. We prove that a number of basic properties shared by bounded expansion and bounded twin-width graphs also hold for bounded merge-width graphs: they are $χ$-bounded, they satisfy the strong Erdős-Hajnal property, and their neighbourhood complexity is linear. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08266 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $χ$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs Bonamy, Marthe Geniet, Colin Combinatorics Discrete Mathematics Merge-width, recently introduced by Dreier and Toruńczyk, is a common generalisation of bounded expansion classes and twin-width for which the first-order model checking problem remains tractable. We prove that a number of basic properties shared by bounded expansion and bounded twin-width graphs also hold for bounded merge-width graphs: they are $χ$-bounded, they satisfy the strong Erdős-Hajnal property, and their neighbourhood complexity is linear. |
| title | $χ$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2504.08266 |