Chromatic numbers of Kneser-type graphs

Dmitriy Zakharov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Let G(n,r,s) be a graph whose vertices are all r-element subsets of an n-element set, in which two vertices are adjacent if they intersect in exactly s elements. In this paper we study chromatic numbers of G(n,r,s) with r,s being fixed constants and n tending to infinity. Using a recent result of Keevash on existence of designs we deduce an inequality [Formula presented] for r>s with r,s fixed constants. This inequality gives sharp upper bounds for r⩽2s+1. Also we develop an elementary approach to this problem and prove that [Formula presented] without use of Keevash's results. Some bounds on the list chromatic number of G(n,r,s) are also obtained.

Original languageEnglish
Article number105188
JournalJournal of Combinatorial Theory, Series A
Volume172
DOIs
StatePublished - May 2020
Externally publishedYes

Keywords

  • Chromatic numbers
  • Distance graphs
  • Existence of designs
  • Johnson graphs
  • Kneser graphs

Fingerprint

Dive into the research topics of 'Chromatic numbers of Kneser-type graphs'. Together they form a unique fingerprint.

Cite this