Let {n_k} be a lacunary sequence, i.e., the ratio of successive elements of the sequence is at least some q>1. In 1987, Erdos asked for the chromatic number of a graph G on the integers, where two integers are connected by an edge iff their difference is in the sequence {n_k}. Y. Katznelson found a connection via a dynamical idea to a Diophantine approximation problem: finding irrationals x such that n_k times x is far from the integers for all k. In joint work with W. Schlag, we improve Katznelson's bounds for both problems using the Lovasz local lemma.