|
Problemy Peredachi Informatsii, 2018, Volume 54, Issue 1, Pages 78–92
(Mi ppi2261)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Received: 06.06.2017 Revised: 27.09.2017
Citation:
A. V. Berdnikov, “Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size”, Probl. Peredachi Inf., 54:1 (2018), 78–92; Problems Inform. Transmission, 54:1 (2018), 70–83
Linking options:
https://www.mathnet.ru/eng/ppi2261 https://www.mathnet.ru/eng/ppi/v54/i1/p78
|
Statistics & downloads: |
Abstract page: | 266 | Full-text PDF : | 34 | References: | 34 | First page: | 11 |
|