Chromatic number of graphs with special distance sets, I

V. Yegnanarayanan


Given a subset \(D\) of positive integers, an integer distance graph is a graph \(G(\mathbb{Z}, D)\) with the set \(\mathbb{Z}\) of integers as vertex set and with an edge joining two vertices \(u\) and \(v\) if and only if \(|u - v| \in D\). In this paper we consider the problem of determining the chromatic number of certain integer distance graphs \(G(\mathbb{Z}, D)\)whose distance set \(D\) is either 1) a set of \((n+1)\) positive integers for which the \(n^{th}\) power of the last is the sum of the \(n^{th}\) powers of the previous terms, or 2) a set of pythagorean quadruples, or 3) a set of pythagorean \(n\)-tuples, or 4) a set of square distances, or 5) a set of abundant numbers or deficient numbers or carmichael numbers, or 6) a set of polytopic numbers, or 7) a set of happy numbers or lucky numbers, or 8) a set of Lucas numbers, or 9) a set of \(\mathcal{U}\)lam numbers, or 10) a set of weird numbers. Besides finding the chromatic number of a few specific distance graphs we also give useful upper and lower bounds for general cases. Further, we raise some open problems.


chromatic number, prime distance graph, unit distance graph

Full Text:



  • There are currently no refbacks.