Email this article Chromatic Numbers of Distance Graphs with Several Forbidden Distances and without Cliques of a Given Size
- Authors: Berdnikov A.V.1
-
Affiliations:
- Moscow Institute of Physics and Technology (State University)
- Issue: Vol 54, No 1 (2018)
- Pages: 70-83
- Section: Large Systems
- URL: https://journal-vniispk.ru/0032-9460/article/view/166487
- DOI: https://doi.org/10.1134/S0032946018010064
- ID: 166487
Cite item
Open Access
Access granted
Subscription Access
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.
About the authors
A. V. Berdnikov
Moscow Institute of Physics and Technology (State University)
Author for correspondence.
Email: alexey-berdnikov@yandex.ru
Russian Federation, Moscow
Supplementary files
