Adjacency labelling for proper minor-closed graph classes
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_ | 1866918488969314304 |
|---|---|
| author | Dujmović, Vida Gavoille, Cyril Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. |
| author_facet | Dujmović, Vida Gavoille, Cyril Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. |
| contents | We show that every proper minor-closed class of graphs admits a $(1+o(1))\log_2 n$-bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $\mathcal{G}$ and every positive integer $n$ there exists an $n^{1+o(1)}$-vertex graph $U$ such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U$. Both results are optimal up to the lower order term. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06616 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Adjacency labelling for proper minor-closed graph classes Dujmović, Vida Gavoille, Cyril Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. Discrete Mathematics Combinatorics We show that every proper minor-closed class of graphs admits a $(1+o(1))\log_2 n$-bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $\mathcal{G}$ and every positive integer $n$ there exists an $n^{1+o(1)}$-vertex graph $U$ such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U$. Both results are optimal up to the lower order term. |
| title | Adjacency labelling for proper minor-closed graph classes |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2605.06616 |