Unit-distance graphs, graphs on the integer lattice and a Ramsey type result
type: Item
instance of: scholarly article
title: Unit-distance graphs, graphs on the integer lattice and a Ramsey type result
zbMATH Open document ID: 0848.05026
DOI: 10.1007/BF01831139
author: Kiran B. Chilakamarri
author: Carolyn R. Mahoney
published in: Aequationes Mathematicae
publication date: 1996-10-06T00:00:00Z
full work available at URL: https://eudml.org/doc/137629
review text: 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.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 856824
zbMATH Keywords: euclidean plane
zbMATH Keywords: unit distance
zbMATH Keywords: chromatic number of the plane
zbMATH Keywords: unit-distance graphs
zbMATH Keywords: integer lattice
zbMATH Keywords: euclidean distance
zbMATH Keywords: clique number
zbMATH Keywords: colorings
reviewed by: Peter Brass
MaRDI profile type: Publication
Wikidata QID: Q56610703
cites work: A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
cites work: Q5808059
OpenAlex ID: W4248902962
description: scientific article; zbMATH DE number 856824