COLORING SOME FINITE SETS IN Rn

被引：20

作者：

Balogh, Jozsef ^{[1
]}

Kostochka, Alexandr ^{[1
,2
]}

Raigorodskii, Andrei ^{[3
,4
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Sobolev Inst Math, Novosibirsk, Russia

[3] Moscow MV Lomonosov State Univ, Dept Mech & Math, Moscow 119991, Russia

[4] Moscow Inst Phys & Technol, Dept Discrete Math, Dolgoprudnyi, Russia

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2013年 / 33卷 / 01期

基金：

俄罗斯基础研究基金会; 美国国家科学基金会;

关键词：

chromatic number; independence number; distance graph; REALIZATION; DISTANCES;

D O I：

10.7151/dmgt.1641

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

This note relates to bounds on the chromatic number chi(R-n) of the Euclidean space, which is the minimum number of colors needed to color all the points in R-n so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs G(n) in R-n was introduced showing that chi(R-n) >= chi(G(n)) >= (1+ 0(1)) n(2)/6. For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that chi(G(n)) similar to n(2)/6 and find an exact formula for the chromatic number in the case of n = 2(k) and n = 2(k) - 1.

引用

页码：25 / 31

页数：7

共 9 条

[1] On the chromatic number of ℝ9 [J].