Unit-distance graphs, graphs on the integer lattice and a Ramsey type result
Graphs realizable by points of euclidean plane as vertices and point pairs at unit distance as edges found interest in several problems of combinatorial geometry, among them the problem of the chromatic number of the plane. A strange characterization of unit-distance graphs was obtained by Chilakamarri who proved that a graph \(G\) is realizable as unit-distance graph in euclidean plane if and only if there is an \(\varepsilon > 0\) such that for each sufficiently large \(r\) the graph \(G\) can be realized with points of the integer lattice \(\mathbb{Z}^2\) as vertices, any two of which have distance at least \(\varepsilon r\), and two vertices \(p,q \in \mathbb{Z}^2\) are joined by an edge iff their euclidean distance is in the interval \([r - \sqrt 2,r + \sqrt 2]\). This paper continues the investigation of this class of graphs (realizable with integer lattice points, which are joined by an edge iff their distance is in the interval \([r - \sqrt 2,r + \sqrt 2])\) by determining the clique number and bounds for the chromatic number and proving a Ramsey-type result for colorings of the integer lattice.
scientific article; zbMATH DE number 856824