On chromatic numbers of nearly Kneser distance graphs
- Authors: Bobu A.V.1, Kupriyanov A.E.1, Raigorodskii A.M.1,2,3
-
Affiliations:
- Mechanics and Mathematics Faculty
- Moscow Institute of Physics and Technology (State University)
- Institute of Mathematics and Computer Science
- Issue: Vol 93, No 3 (2016)
- Pages: 267-269
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/223694
- DOI: https://doi.org/10.1134/S1064562416030091
- ID: 223694
Cite item
Abstract
A family of distance graphs whose structure is close to that of Kneser graphs is studied. New lower and upper bounds for the chromatic numbers of such graphs are obtained, and relations between these numbers are considered. The structure of certain important independent sets of the family of graphs under consideration is described, and the cardinalities of these sets are explicitly calculated.
About the authors
A. V. Bobu
Mechanics and Mathematics Faculty
Author for correspondence.
Email: a.v.bobu@gmail.com
Russian Federation, Moscow, 119991
A. E. Kupriyanov
Mechanics and Mathematics Faculty
Email: a.v.bobu@gmail.com
Russian Federation, Moscow, 119991
A. M. Raigorodskii
Mechanics and Mathematics Faculty; Moscow Institute of Physics and Technology (State University); Institute of Mathematics and Computer Science
Email: a.v.bobu@gmail.com
Russian Federation, Moscow, 119991; Institutskii per. 9, Dolgoprudnyi, Moscow oblast, 141700; ul. Ranzhurova 5a, Ulan-Ude, 670000