  Let ${n_k}$ be an increasing lacunary sequence, i.e., $n_{k+1}/n_k>1+r$ for
some $r>0$. In 1987, P. Erdos asked for the chromatic number of a graph $G$ on
the integers, where two integers $a,b$ are connected by an edge iff their
difference $|a-b|$ is in the sequence ${n_k}$. Y. Katznelson found a connection
to a Diophantine approximation problem (also due to Erdos): the existence of
$x$ in $(0,1)$ such that all the multiples $n_j x$ are at least distance
$\delta(x)>0$ from the set of integers. Katznelson bounded the chromatic number
of $G$ by $Cr^{-2}|\log r|$. We apply the Lov\'asz local lemma to establish
that $\delta(x)>cr|\log r|^{-1}$ for some $x$, which implies that the chromatic
number of $G$ is at most $Cr^{-1} |\log r|$. This is sharp up to the
logarithmic factor.
