Let $D\subseteq\mathbb{N}^+$, and consider the graph $G\_D$ with vertices set $\mathbb{N}$ and edges set $\{(x,y)\in\mathbb{N}\times\mathbb{N}\;s.t.\;|x-y|\in D\}$. I expect that if $D$ is dense enough in $\mathbb{N}^+$, then the chromatic number of $G\_D$ is large. As Wojowu pointed out in the comments, positive density does not guarantee infinite chromatic number. Hence, one can ask the following question:


**if $D$ has density (say, e.g., lower asymptotic density) one in $\mathbb{N}^+$, is it true that the chromatic number of $G\_D$ is infinite?**


Thank you for any suggestion.



Chromatic number of distance graphs over the integers
I'll show that if $G\_D$ has chromatic number $k$ then $D$ has upper Banach density at most $(k-1)/k$. 


So suppose $G\_D$ has chromatic number $k$. Let $\mathbb{N}$ be partitioned into $P\_1,\ldots,P\_k$, where each $P\_i$ is independent with respect to $G\_D$. Without loss of generality, $P:=P\_1$ has upper Banach density at least $1/k$. Let $Q=\{|x-y|:x,y\in P\text{ are distinct}\}$. Then $Q\subseteq \mathbb{N}^+\backslash D$ since $P$ is $G\_D$-independent. We claim that $Q$ has lower Banach density at least $1/k$, which implies the desired result for $D$.


(The proof of the claim is an adaptation of Ruzsa's Covering Lemma and/or the well-known fact that if a set $A$ of integers has positive upper Banach density then $A-A$ is syndetic.)


Call a set $X\subset\mathbb{N}$ *$P$-separating* if $(x+P)\cap (y+P)=\emptyset$ for all distinct $x,y\in X$. Since $P$ has upper Banach density at least $1/k$, it follows that any $P$-separating subset of $\mathbb{N}$ has size at most $k$. So we may choose a $P$-separating set $X$ of maximal size. Now fix $a\in\mathbb{N}^+$ such that $a>\max X$. By maximality, there is some $x\in X$ such that $(a+P)\cap (x+P)\neq\emptyset$. So there are $p,q\in P$ such that $a+p=x+q$. Since $a>x$ it follows that $a\in x+Q$. 


Altogether, we have shown that $X+Q$ is cofinite in $\mathbb{N}^+$. Since $|X|\leq k$, it follows that $Q$ has lower Banach density at least $1/k$. 


  



*Remark.* The proof actually shows that if $G\_D$ has chromatic number $k$ then there are $k$ translates of the complement of $D$ whose union is cofinite in $\mathbb{N}^+$, which I suppose is stronger than saying $D$ has upper Banach density at most $(k-1)/k$. 


