Coloring some finite sets in Rn

József Balogh, Alexandr Kostochka, Andrei Raigorodskii

Research output: Contribution to journalArticlepeer-review


This note relates to bounds on the chromatic number χ(Rn) of the Eu- clidean space, which is the minimum number of colors needed to color all the points in Rn so that any two points at the distance 1 receive differ- ent colors. In [6] a sequence of graphs Gn in Rn was introduced showing that χ(Rn) ≥ χ(Gn) ≥ (1 + o(1))n2/6 . For many years, this bound has been remaining the best known bound for the chromatic numbers of some low- dimensional spaces. Here we prove that χ(Gn) ~ n2/6 and find an exact formula for the chromatic number in the case of n = 2k and n = 2k - 1. Keywords: chromatic number, independence number, distance graph.

Original languageEnglish (US)
Pages (from-to)25-31
Number of pages7
JournalDiscussiones Mathematicae - Graph Theory
Issue number1
StatePublished - 2013


  • Chromatic number
  • Independence number
  • Sistance graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this