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.
Язык оригиналаАнглийский
Номер статьи4
ЖурналDiscrete Mathematics
Том347
Номер выпуска4
DOI
СостояниеОпубликовано - 1 апр 2024

ID: 117803773