On distance graphs with large chromatic numbers and small clique numbers
Автор: Zvonarev A.E., Raigorodskii A.M.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Хроматические числа пространств
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
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