Projective Chromatic Numbers

Abstract

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 $\hat{\mathbf{I}}{”}_n^1$-definable well-order of the reals implies $\ddot{I}{‡}_{\hat{\mathbf{I}}{”}_{\mathbf{n}}^1}(G)=\ddot{I}‡(G)$ for all locally countable $\hat{\mathbf{I}}{”}_{\mathbf{n}}^1$-definable graphs $G$, and that the presence of a $\hat{\mathbf{I}}{”}_2^1$-definable well-order of the reals implies $\ddot{I}{‡}_{\hat{\mathbf{I}}{”}_2^1}(G)=\ddot{I}‡(G)$ for all locally countable Borel graphs $G$.

21 pages