TY - JOUR

T1 - Trivial colors in colorings of Kneser graphs

AU - Kiselev, S.

AU - Kupavskii, A.

N1 - Export Date: 21 March 2024 CODEN: DSMHA Адрес для корреспонденции: Kupavskii, A.; Saint-Petersburg State UniversityRussian Federation; эл. почта: kupavskii@ya.ru Сведения о финансировании: Russian Science Foundation, RSF, N 22-11-00131 Текст о финансировании 1: The research was in part funded by the grant of the Russian Science Foundation N 22-11-00131 .

PY - 2024/4/1

Y1 - 2024/4/1

N2 - 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.

AB - 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.

KW - Kneser colorings

KW - Kneser graphs

KW - Non-trivial intersecting families

UR - https://www.mendeley.com/catalogue/054a56c5-7753-3d4d-90d8-11f4c1a9032e/

U2 - 10.1016/j.disc.2023.113869

DO - 10.1016/j.disc.2023.113869

M3 - статья

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 4

M1 - 4

ER -