Email this article On chromatic numbers of close-to-Kneser distance graphs
- Authors: Bobu A.V.1, Kupriyanov A.E.1
-
Affiliations:
- Department of Mathematical Statistics and Random Processes, Faculty of Mathematics and Mechanics
- Issue: Vol 52, No 4 (2016)
- Pages: 373-390
- Section: Large Systems
- URL: https://journal-vniispk.ru/0032-9460/article/view/166338
- DOI: https://doi.org/10.1134/S0032946016040050
- ID: 166338
Cite item
Open Access
Access granted
Subscription Access
Abstract
We study a family of distance graphs whose structure is close to that of Kneser graphs. We give new lower and upper bounds on the chromatic numbers of such graphs and consider the question of their interrelation. We also describe the structure of some important independence sets for this family of graphs and explicitly compute their cardinalities.
About the authors
A. V. Bobu
Department of Mathematical Statistics and Random Processes, Faculty of Mathematics and Mechanics
Author for correspondence.
Email: a.v.bobu@gmail.com
Russian Federation, Moscow
A. E. Kupriyanov
Department of Mathematical Statistics and Random Processes, Faculty of Mathematics and Mechanics
Email: a.v.bobu@gmail.com
Russian Federation, Moscow
Supplementary files
