Minimal definable graphs of definable chromatic number at least three
2021
We show that there is a Borel graph on a standard Borel space of Borel chromatic number three that admits a Borel homomorphism to every analytic graph on a standard Borel space of Borel chromatic number at least three. Moreover, we characterize the Borel graphs on standard Borel spaces of vertex-degree at most two with this property, and show that the analogous result for digraphs fails.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
20
References
1
Citations
NaN
KQI