Coloring of distance graphs with intervals as distance sets (Q2567207)

The distance graph \(G(\mathbb Z,D)\) has vertex set \(\mathbb Z\) and two vertices \(x\) and \(y\) are adjacent if and only if their distance \(d(x,y)=| x-y| \) is an element of the so-called distance set \(D \subseteq \mathbb N\). The authors investigate the chromatic number, the fractional chromatic number and the circular chromatic number of distance graphs \(G(\mathbb Z,D)\) with distance sets \(D=D_{m,[k,k']}=\{1,2,\dots,m\}-\{k,k+1,\dots,k'\}\). A circular coloring of a graph \(G\) is a generalization of a vertex coloring and is defined as an assignment \(c\) of open unit length arcs of a circle \(C\) to the vertices of \(G\) such that \(c(x)\cap c(y)=\emptyset\) whenever the vertices \(x\) and \(y\) are adjacent. In particular, the chromatic number of \(G(\mathbb Z,D_{m,[2,k']})\) is completely determined in this paper.