Trivial colors in colorings of Kneser graphs
Sergei Kiselev, Andrey Borisovich Kupavskii · Discrete Mathematics · 2024
We show that any proper coloring of a Kneser graph K G n , k with n − 2 k + 2 colors contains a trivial color class (i.e., a color class consisting of sets that all contain a fixed element), provided n > ( 2 + ε ) k 2 , 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 K G n , k .