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.
This publication is cited in the following 6 articles:
A. M. Raigorodskii, D. D. Cherkashin, “Extremal problems in hypergraph colourings”, Russian Math. Surveys, 75:1 (2020), 89–146
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “A Generalization of Kneser Graphs”, Math. Notes, 107:3 (2020), 392–403
B. Bresar, N. Gastineau, S. Klavzar, O. Togni, “Exact distance graphs of product graphs”, Graphs Comb., 35:6 (2019), 1555–1569
H. R. Daneshpajouh, “On the chromatic number of generalized kneser hypergraphs”, Eur. J. Comb., 81 (2019), 150–155
J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general kneser graphs and hypergraphs via high-discrepancy hypergraphs”, Eur. J. Comb., 79 (2019), 228–236
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “On the number of edges of a uniform hypergraph with a range of allowed intersections”, Problems Inform. Transmission, 53:4 (2017), 319–342
Citation in format AMSBIB
Contact us: