This article is cited in 6 papers

Large Systems

On chromatic numbers of close-to-Kneser distance graphs

A. V. Bobu, A. E. Kupriyanov

Department of Mathematical Statistics and Random Processes, Faculty of Mathematics and Mechanics, Lomonosov Moscow State University, Moscow, Russia

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.

UDC: 621.391.1+519.174.7

Received: 04.02.2016
Revised: 14.05.2016

 English version: Problems of Information Transmission, 2016, 52:4, 373–390

Bibliographic databases:

• 
• 
•