CaltechAUTHORS
Published January 28, 2021 | Submitted + Published
Journal Article Open

Minimal definable graphs of definable chromatic number at least three

Carroy, Raphaël
Miller, Benjamin D.
Schrittesser, David
Vidnyánszky, Zoltán
An error occurred while generating the citation.

Abstract

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.

Additional Information

© The Author(s), 2021. Published by Cambridge University Press. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited. Received: 26 November 2019; Revised: 14 September 2020; Accepted: 5 October 2020. The authors were supported in part by FWF Grants P28153 and P29999. R. Carroy was supported by PRIN grant number 2017NWTM8R. Z. Vidnyánszky was also supported by NKFIH, grant nos. 113047 and 129211 and FWF Grant M2779. Conflict of Interest: None.

Attached Files

Published - minimal-definable-graphs-of-definable-chromatic-number-at-least-three.pdf

Submitted - 1906.08373.pdf

Files

minimal-definable-graphs-of-definable-chromatic-number-at-least-three.pdf
Files (784.8 kB)
Name Size Download all
md5:55e929543bc525b005da5cbaa53b530b
467.3 kB Preview Download
md5:834f552e341d8d41efa8d53c7cf71ba9
317.5 kB Preview Download

Additional details

Identifiers Related works Funding Dates
Created:
August 22, 2023
Modified:
October 23, 2023