Borel line graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912125262233600 |
|---|---|
| author | Anderson, James Bernshteyn, Anton |
| author_facet | Anderson, James Bernshteyn, Anton |
| contents | We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph associated to the equivalence relation $\mathbb{E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman--Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_07893 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Borel line graphs Anderson, James Bernshteyn, Anton Logic Combinatorics We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph associated to the equivalence relation $\mathbb{E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman--Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers. |
| title | Borel line graphs |
| topic | Logic Combinatorics |
| url | https://arxiv.org/abs/2310.07893 |