Let $X$ be a Polish space and let $G\in\mathbf{\Sigma}^1_1(X^2)$ be a graph on $X$, that is an irreflexive and symmetric relation on $X$.
Given a cardinal $\kappa$ we say that $G$ has chromatic number $\kappa$, in symbols $\chi(G)=\kappa$, if there is a function $\varphi\colon X\to Y$ for some Polish space $Y$ such that $|\varphi(X)|=\kappa$ and for every $y\in\varphi(X)$, we have that $\varphi^{-1}(y)$ is $G$-independent, meaning that $G\cap(\varphi^{-1}(y))^2=\varnothing$, and $\kappa$ is the least cardinal with this property. We say that $G$ has Borel chromatic number $\kappa$, in symbols $\chi_B(G)=\kappa$ if we additionally require $\varphi$ to be Borel (of course the fact that $Y$ is Polish is completely irrelevant in the definition of $\chi(G)$ and I'm only phrasing it this way to define $\chi_B(G)$ analogously).
Question: Does $\mathsf{ZFC}$ prove that $\chi(G)\in\{1,2,\ldots,\aleph_0,2^{\aleph_0}\}$? Of course the answer is positive under $\mathsf{CH}$ but that is hardly interesting.
Remarks:
- If $\mathsf{CH}$ fails and there are no regularity assumption on $G$ then there are trivial counterexamples, fix $A\subseteq\Bbb R$ with $|A|=\aleph_1$ and let $G=A^2\setminus\Delta_\Bbb R$. Then $\chi(G)=\aleph_1$ but $G$ is not analytic.
- The same question for $\chi_B(G)$ (or even for Baire measurable colourings) has a positive answer by the Kechris-Solecki-Todorcevic $G_0$-dichotomy.
- $\chi(G)$ and $\chi_B(G)$ can be wildly different, there are examples with $\chi(G)=2$ ($G$ can even be taken to be acyclic) and $\chi_B(G)=2^{\aleph_0}$.
