Coloring some finite sets in Rn

József Balogh; Alexandr Kostochka; Andrei Raigorodskii

doi:10.7151/dmgt.1641

Coloring some finite sets in Rn

József Balogh, Alexandr Kostochka, Andrei Raigorodskii

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

This note relates to bounds on the chromatic number χ(Rⁿ) of the Eu- clidean space, which is the minimum number of colors needed to color all the points in Rⁿ so that any two points at the distance 1 receive differ- ent colors. In [6] a sequence of graphs G_n in Rⁿ was introduced showing that χ(Rⁿ) ≥ χ(G_n) ≥ (1 + o(1))n²/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 χ(G_n) ~ n²/6 and find an exact formula for the chromatic number in the case of n = 2^k and n = 2^k - 1. Keywords: chromatic number, independence number, distance graph.

Original language	English (US)
Pages (from-to)	25-31
Number of pages	7
Journal	Discussiones Mathematicae - Graph Theory
Volume	33
Issue number	1
DOIs	https://doi.org/10.7151/dmgt.1641
State	Published - 2013

Keywords

Chromatic number
Independence number
Sistance graph

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.7151/dmgt.1641

Library availability

Discover UIUC Full Text

Cite this

@article{b65b07127aee4242a28e2742d58c2ba2,

title = "Coloring some finite sets in Rn",

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.",

keywords = "Chromatic number, Independence number, Sistance graph",

author = "J{\'o}zsef Balogh and Alexandr Kostochka and Andrei Raigorodskii",

note = "Funding Information: 1Research of this author is supported in part by NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grant 11067, and OTKA Grant K76099. 2Research of this author is supported in part by NSF grant DMS-0965587 and by the Ministry of education and science of the Russian Federation (Contract no. 14.740.11.0868). 3Research of this author is supported in part by the grant of the President of Russian Federation (Contract no. NSh-2519.2012.1) and by the grant of the Russian Foundation for Basic Research (Contract no. 12-01-00683).",

year = "2013",

doi = "10.7151/dmgt.1641",

language = "English (US)",

volume = "33",

pages = "25--31",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

TY - JOUR

T1 - Coloring some finite sets in Rn

AU - Balogh, József

AU - Kostochka, Alexandr

AU - Raigorodskii, Andrei

N1 - Funding Information: 1Research of this author is supported in part by NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grant 11067, and OTKA Grant K76099. 2Research of this author is supported in part by NSF grant DMS-0965587 and by the Ministry of education and science of the Russian Federation (Contract no. 14.740.11.0868). 3Research of this author is supported in part by the grant of the President of Russian Federation (Contract no. NSh-2519.2012.1) and by the grant of the Russian Foundation for Basic Research (Contract no. 12-01-00683).

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Independence number

KW - Sistance graph

UR - http://www.scopus.com/inward/record.url?scp=84876374907&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876374907&partnerID=8YFLogxK

U2 - 10.7151/dmgt.1641

DO - 10.7151/dmgt.1641

M3 - Article

AN - SCOPUS:84876374907

SN - 1234-3099

VL - 33

SP - 25

EP - 31

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 1

ER -

Coloring some finite sets in Rn

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this