Chromatic Numbers of Some Distance Graphs

D. A. Zakharov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


For positive integers n > r > s, G(n, r, s) is the graph whose vertices are the r-element subsets of an n-element set, two subsets being adjacent if their intersection contains exactly s elements. We study the chromatic numbers of this family of graphs. In particular, the exact value of the chromatic number of G(n, 3, 2) is found for infinitely many n. We also improve the best known upper bounds for chromatic numbers for many values of the parameters r and s and for all sufficiently large n.

Original languageEnglish
Pages (from-to)238-246
Number of pages9
JournalMathematical Notes
Issue number1-2
StatePublished - Jan 1 2020
Externally publishedYes


  • chromatic number
  • distance graph
  • upper bound


Dive into the research topics of 'Chromatic Numbers of Some Distance Graphs'. Together they form a unique fingerprint.

Cite this