RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2015 Volume 51, Issue 2, Pages 86–98 (Mi ppi2172)

This article is cited in 7 papers

Large Systems

Independence numbers and chromatic numbers of some distance graphs

A. V. Bobu, O. A. Kostina, A. E. Kupriyanov

Department of Mathematical Statistics and Random Processes, Faculty of Mathematics and Mechanics, Lomonosov Moscow State University, Moscow, Russia

Abstract: We study a family of distance graphs in $\mathbb R^n$. We present bounds for independence numbers which are asymptotically tight as $n\to\infty$. We substantially improve upper bounds on chromatic numbers of these graphs, and in a number of cases we give explicit constructions of independence sets.

UDC: 621.391.1+519.1

Received: 28.05.2014


 English version:
Problems of Information Transmission, 2015, 51:2, 165–176

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025