Mathematical Research Letters

Volume 23 (2016)

Number 6

A bound on measurable chromatic numbers of locally finite Borel graphs

Pages: 1633 – 1644

DOI: https://dx.doi.org/10.4310/MRL.2016.v23.n6.a3

Authors

Clinton T. Conley (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania, U.S.A.)

Benjamin D. Miller (Kurt Gödel Research Center for Mathematical Logic, Universität Wien, Austria)

Abstract

We show that the Baire measurable chromatic number of every locally finite Borel graph on a non-empty Polish space is strictly less than twice its ordinary chromatic number, provided this ordinary chromatic number is finite. In the special case that the connectedness equivalence relation is hyperfinite, we obtain the analogous result for the $\mu$-measurable chromatic number.

Keywords

Baire measurable, chromatic number, coloring, graph, locally finite, measurable

2010 Mathematics Subject Classification

Primary 03E15. Secondary 28A05.

Accepted 9 June 2015

Published 21 February 2017