Two dichotomy theorems on colourability of non-analytic graphs
Volume 154 / 1997
Fundamenta Mathematicae 154 (1997), 183-201 DOI: 10.4064/fm-154-2-183-201
We prove: Theorem 1. Let κ be an uncountable cardinal. Every κ-Suslin graph G on reals satisfies one of the following two requirements: (I) G admits a κ-Borel colouring by ordinals below κ; (II) there exists a continuous homomorphism (in some cases an embedding) of a certain locally countable Borel graph $G_0$ into G. Theorem 2. In the Solovay model, every OD graph G on reals satisfies one of the following two requirements: (I) G admits an OD colouring by countable ordinals; (II) as above.