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

Minimal definable graphs of definable chromatic number at least three

Creators

  • 1. ROR icon University of Turin
  • 2. ROR icon University of Vienna

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

1906.08373.pdf

Files (784.8 kB)

Name Size
md5:834f552e341d8d41efa8d53c7cf71ba9
317.5 kB Preview Download
md5:55e929543bc525b005da5cbaa53b530b
467.3 kB Preview Download

Additional details

Identifiers

Eprint ID
108314
Resolver ID
CaltechAUTHORS:20210304-150950107

Related works

Describes
https://arxiv.org/abs/1906.08373 (URL)

Funding

Fonds Zur Förderung der Wissenschaftlichen Forschung (FWF)
P28153
Fonds Zur Förderung der Wissenschaftlichen Forschung (FWF)
P29999
Ministero dell'Università e della Ricerca (MIUR)
2017NWTM8R
National Research, Development and Innovation Fund (NKFIA)
113047
National Research, Development and Innovation Fund (NKFIA)
129211
Fonds Zur Förderung der Wissenschaftlichen Forschung (FWF)
M2779
National Research, Development and Innovation Office (Hungary)

Dates

Created
2021-03-04
Created from EPrint's datestamp field
Updated
2021-11-16
Created from EPrint's last_modified field