\(T\)-Colorings and Chromatic Number of Distance Graphs

We present connections between \(T\)-colorings of graphs and regular vertex-coloring for distance graphs. Given a non-negative integral set \(T\) containing \(0\), a \(T\)-coloring of a simple graph assigns each vertex a non-negative integer (color) such that the difference of colors of adjacent vertices cannot fall in \(T\). Let \(\omega(T)\) be the minimum span of a \(T\)-coloring of an \(n\)-vertex complete graph. It is known that the asymptotic coloring efficiency of \(T\), \(R(T) = \lim_{n\to\infty} \frac{\omega(n)}{n}\), exists for any \(T\). Given a positive integral set \(D\), the distance graph \(G(\mathcal{Z}, D)\) has as vertex set all integers \(\mathbb{Z}\), and two vertices are adjacent if their difference is in \(D\). We prove that the chromatic number of \(G(\mathcal{Z}, D)\), denoted as \(\chi(\mathcal{Z}, D)\), is an upper bound of \(\lceil R(T) \rceil\), provided \(D=T \setminus \{0\}\). This connection is used in calculating \(\chi_a(m, k)\), chromatic number of \(G(\mathcal{Z},D)\) as \(D = \{1,2,3,\ldots,m\} \setminus \{k\}\), \(m > k\). Early results about \(\chi_\beta(m,k)\) were due to Eggleton, Erdos and Skilton [1985] who determined \(\chi_\beta(m,k)\) as \(k = 1\), partially settled the case \(k = 2\), and obtained upper and lower bounds for other cases. We show that \(\chi_\beta(m, k) = k\), if \(m < 2k\); and \(\chi_\beta(m,k) = \lceil \frac{m+k+1}{2} \rceil\), if \(m \geq 2k\) and \(k\) is odd. Furthermore, complete solutions for \(k = 2\) and \(4\), and partial solutions for other even numbers \(k\) are obtained. All the optimal proper colorings presented are periodic with smallest known periods.