Coloring some finite sets in Rn

József Balogh, Alexandr Kostochka, Andrei Raigorodskii

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume33
Issue number1
DOIs
StatePublished - 2013

Keywords

  • Chromatic number
  • Independence number
  • Sistance graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Coloring some finite sets in Rn'. Together they form a unique fingerprint.

Cite this