Definable Kőnig theorems

Abstract

Let $X$ be a Polish space with Borel probability measure $\mu ,$ and let $G$ be a Borel graph on $X$ with no odd cycles and maximum degree $\Delta (G).$ We show that the Baire measurable edge chromatic number of $G$ is at most $\Delta (G)+1$, and if $G$ is $\mu$-hyperfinite then the $\mu$-measurable edge chromatic number obeys the same bound. More generally, we show that $G$ has Borel edge chromatic number at most $\Delta (G)$ plus its asymptotic separation index.

6 pages