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.
Minimal definable graphs of definable chromatic number at least three
Carroy R.;
2021-01-01
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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Minimal-definable-graphs-of-definable-chromatic-number-at-least-threeForum-of-Mathematics-Sigma.pdf
Accesso aperto
Descrizione: pdf editoriela
Tipo di file:
PDF EDITORIALE
Dimensione
444.89 kB
Formato
Adobe PDF
|
444.89 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
