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}$.



On the chromatic number of an analytic graph
There is a counterexample due to Todorcevic. See Proposition 9.2 in Kechris, Solecki, Todorcevic, Borel Chromatic Numbers, Advances in Mathematics, Vol. 141, Issue 1, 1999, Pages 1-44


