Coloring Distance Graphs and Graphs of Diameters

Andrei M. Raigorodskii ()
Additional contact information
Andrei M. Raigorodskii: Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 429-460 from Springer

Abstract: Abstract In this chapter, we discuss two classical problems lying on the edge of graph theory and combinatorial geometry. The first problem is due to E. Nelson. It consists of coloring metric spaces in such a way that pairs of points at some prescribed distances receive different colors. The second problem is attributed to K. Borsuk and involves finding the minimum number of parts of smaller diameter into which an arbitrary bounded nonsingleton point set in a metric space can be partitioned. Both problems are easily translated into the language of graph theory, provided we consider, instead of the whole space, any (finite) distance graph or any (finite) graph of diameters. During the last decades, a huge number of ideas have been proposed for solving both problems, and many results in both directions have been obtained. In the survey below, we try to give an entire picture of this beautiful area of geometric combinatorics.

Keywords: Lower Estimate; Chromatic Number; Distance Graph; Independence Number; Voronoi Region (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_23

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_23

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().