On the Chromatic Number for a Set of Metric Spaces

I. M. Mitricheva (Shitova)

M. V. Lomonosov Moscow State University

Abstract: We study the problem of finding the chromatic number of a metric space with a forbidden distance. Using the linear-algebraic technique in combinatorics and convex optimization methods, we obtain a set of new estimates and observe the change of the asymptotic lower bound for the chromatic number of Euclidean space under the continuous change of the metric from $l_1$ to $l_2$.

Keywords: metric space with a forbidden distance, chromatic number, convex optimization, Euclidean space, graph, Karush–Kuhn–Tucker theorem, Lagrange function.

UDC: 514.177.2+519.157+519.174.7

Received: 15.04.2009

DOI: 10.4213/mzm8602

 English version: Mathematical Notes, 2012, 91:3, 399–408

Bibliographic databases:

• 
• 
• 
• 
•