Аннотация:
Рассматриваются графы расстояний в $n$-мерном пространстве с $p$-нормой c $k$ запрещенными расстояниями, не содержащие клик фиксированного размера. С помощью вероятностной конструкции производится построение графов такого вида, имеющих хроматическое число не меньше $(Bk)^{Cn}$, где $B$ и $C$ – некоторые константы.
УДК:
621.391.1+519.1
Поступила в редакцию: 06.06.2017 После переработки: 27.09.2017