Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion
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_ | 1866908949277573120 |
|---|---|
| author | Karol, Nikolai Wood, David R. |
| author_facet | Karol, Nikolai Wood, David R. |
| contents | We prove that sparse string graphs in a fixed surface have linear expansion. We extend this result to the more general setting of sparse region intersection graphs over any proper minor-closed class. The proofs are combinatorial and self-contained, and provide bounds that are within a constant factor of optimal. Applications of our results to graph colouring are presented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_07903 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion Karol, Nikolai Wood, David R. Combinatorics Discrete Mathematics We prove that sparse string graphs in a fixed surface have linear expansion. We extend this result to the more general setting of sparse region intersection graphs over any proper minor-closed class. The proofs are combinatorial and self-contained, and provide bounds that are within a constant factor of optimal. Applications of our results to graph colouring are presented. |
| title | Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2604.07903 |