Research output: Contribution to journal › Article › peer-review
Trivial colors in colorings of Kneser graphs. / Kiselev, S.; Kupavskii, A.
In: Discrete Mathematics, Vol. 347, No. 4, 4, 01.04.2024.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 117803773