[latexpage]

The chromatic number $\chi(G)$ of a graph $G$ is the minimal number of colors in a proper vertex coloring
(neighbors assigned distinct colors.)

Problem A (Erdos, 1987):
Fix $\epsilon>0$ and suppose $ \{n_j\}_{j=1}^\infty$ is a   lacunary sequence of
positive integers, where $n_{j+1}>(1+\epsilon) n_j$ for all $j \ge 1$.

Is the chromatic number~$\chi(G)$ necessarily finite?   

 Problem B (Erdos, 1975): 
Let $\eps>0$ and let $\{n_j\}_{j=1}^{\infty}$  be as in Problem A.
Is there a number $\theta\in(0,1)$ so that the sequence
$\{n_j \theta\}_{j=1}^\infty$ is not dense modulo $ 1$? 

The answer to both problems is positive. Indeed, if the  distance from $n_j \theta$ to the nearest integer is at least $\delta$ for all $j$, then $\chi(G) \le 1+1/\delta$. 

Khinchin, and independently,  Katznelson, proved a lower bound of $\epsilon^{-2}$ for $\delta$, and this was improved to $\epsilon/(|\log \epsilon|)$ by Peres and Schlag. Is the logarithmic term needed?

 

REFERENCES