This article is cited in 1 paper

Large Systems

Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size

A. V. Berdnikov

Moscow Institute of Physics and Technology (State University), Dolgoprudny, Russia

Abstract: We consider distance graphs with $k$ forbidden distances in an $n$-dimensional space with the $p$-norm that do not contain cliques of a fixed size. Using a probabilistic construction, we present graphs of this kind with chromatic number at least $(Bk)^{Cn}$, where $B$ and $C$ are constants.

UDC: 621.391.1+519.1

Received: 06.06.2017
Revised: 27.09.2017

 English version: Problems of Information Transmission, 2018, 54:1, 70–83

Bibliographic databases:

• 
• 
•