We show that any proper coloring of a Kneser graph KGn,k with n−2k+2 colors contains a trivial color class (i.e., a color class consisting of sets that all contain a fixed element), provided n>(2+ε)k2, where ε→0 as k→∞. This bound is essentially tight. This is a consequence of a more general result on the minimum number of non-trivial color classes needed to properly color KGn,k. © 2024 Elsevier B.V.
Original languageEnglish
Article number4
JournalDiscrete Mathematics
Volume347
Issue number4
DOIs
StatePublished - 1 Apr 2024

    Research areas

  • Kneser colorings, Kneser graphs, Non-trivial intersecting families

ID: 117803773