Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-19T02:35:34.664Z Has data issue: false hasContentIssue false

Minimal definable graphs of definable chromatic number at least three

Published online by Cambridge University Press:  28 January 2021

Raphaël Carroy
Affiliation:
Raphaël Carroy, Dipartimento di Matematica “Giuseppe Peano”, Università degli studi di Torino Palazzo Campana, Via Carlo Alberto 10, 10123 Torino, Italy, E-mail: raphael.carroy@univie.ac.at; http://www.logique.jussieu.fr/~carroy/indexeng.html
Benjamin D. Miller
Affiliation:
University of Vienna, Department of Mathematics, Oskar Morgenstern Platz 1, Wien 1090, Austria, E-mail: benjamin.miller@univie.ac.at; https://homepage.univie.ac.at/benjamin.miller/
David Schrittesser
Affiliation:
University of Vienna, Department of Mathematics, Oskar Morgenstern Platz 1, Wien 1090, Austria, E-mail: david.schrittesser@univie.ac.at; http://homepage.univie.ac.at/david.schrittesser/
Zoltán Vidnyánszky
Affiliation:
University of Vienna, Department of Mathematics, Oskar Morgenstern Platz 1, Wien 1090, Austria; and California Institute of Technology, Department of Mathematics, Pasadena, CA 91125, E-mail: zoltan.vidnyanszky@univie.ac.at; http://www.logic.univie.ac.at/~vidnyanszz77/

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Foundations
Creative Commons
Creative Common License - CCCreative Common License - BY
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.
Copyright
© The Author(s), 2021. Published by Cambridge University Press