RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2018, том 54, выпуск 1, страницы 78–92 (Mi ppi2261)

Эта публикация цитируется в 1 статье

Большие системы

Хроматические числа графов расстояний с несколькими запрещенными расстояниями без клик заданного размера

А. В. Бердников

Московский физико-технический институт (государственный университет)

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

УДК: 621.391.1+519.1

Поступила в редакцию: 06.06.2017
После переработки: 27.09.2017


 Англоязычная версия: Problems of Information Transmission, 2018, 54:1, 70–83

Реферативные базы данных:


© МИАН, 2024