On distance graphs with large chromatic numbers and small clique numbers

Бесплатный доступ

The work is concerned with the study of the chromatic number χ(Rn) of the Euclidean space. The quantity is defined as the minimum number of colors needed for a coloring of points in Rn such that any two points at distance 1 from each other have different colors. It is known that χ(Rn) ≥ (ζ+o(1))n, where ζ = 1.239... This is equivalent to the existence of an n-dimensional distance graph (vertices are points and edges are segments of length 1) with chromatic number (ζ +o(1))n. We prove much more: there exists a distance graph with chromatic number (ζ +o(1))n and without cliques of growing size.

Chromatic number of a space, distance graph, graph without cliques, ramsey theory

Короткий адрес: https://sciup.org/142186201

IDR: 142186201

Статья научная