Projective Chromatic Numbers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915952278372352 |
|---|---|
| author | Rettich, Adrian Serafin, Luke |
| author_facet | Rettich, Adrian Serafin, Luke |
| contents | We extend classical notions of definable colourability of graphs to the general projective setting and investigate whether known results, mainly about the $G_0$ dichotomy and the $2n + 1$ conjecture, hold in the context of higher projective pointclasses. We establish that for $n \ge 2$, the presence of a $\mathbfΔ^1_n$-definable well-order of the reals implies $χ_{\mathbf{Δ^1_n}}(G) = χ(G)$ for all locally countable $\mathbf{Δ^1_n}$-definable graphs $G$, and that the presence of a $\mathbf{Δ^1_2}$-definable well-order of the reals implies $χ_{\mathbf{Δ^1_2}}(G) = χ(G)$ for all locally countable Borel graphs $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21813 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Projective Chromatic Numbers Rettich, Adrian Serafin, Luke Logic 03E15, 05C15 We extend classical notions of definable colourability of graphs to the general projective setting and investigate whether known results, mainly about the $G_0$ dichotomy and the $2n + 1$ conjecture, hold in the context of higher projective pointclasses. We establish that for $n \ge 2$, the presence of a $\mathbfΔ^1_n$-definable well-order of the reals implies $χ_{\mathbf{Δ^1_n}}(G) = χ(G)$ for all locally countable $\mathbf{Δ^1_n}$-definable graphs $G$, and that the presence of a $\mathbf{Δ^1_2}$-definable well-order of the reals implies $χ_{\mathbf{Δ^1_2}}(G) = χ(G)$ for all locally countable Borel graphs $G$. |
| title | Projective Chromatic Numbers |
| topic | Logic 03E15, 05C15 |
| url | https://arxiv.org/abs/2604.21813 |