Local Coloring Problems on Smooth Graphs

Abstract

We construct a smooth locally finite Borel graph $G$ and a local coloring problem $\Pi$ such that $G$ has a coloring $V(G)\to \mathbb{N}$ that solves $\Pi$, but no such coloring can be Borel.

5 pages, 1 figure