Research output: Contribution to journal › Article › peer-review
Two questions on Kneser colorings. / Inozemtsev, E.; Kupavskii, A.
In: Discrete Mathematics, Vol. 349, No. 2, 01.02.2026.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Two questions on Kneser colorings
AU - Inozemtsev, E.
AU - Kupavskii, A.
N1 - Export Date: 29 March 2026; Cited By: 0; Correspondence Address: A. Kupavskii; Moscow Institute of Physics and Technology, Saint-Petersburg State University, Innopolis University, Russian Federation; email: kupavskii@ya.ru; CODEN: DSMHA
PY - 2026/2/1
Y1 - 2026/2/1
N2 - In this paper, we investigate two questions on Kneser graphs KGn,k. First, we prove that the union of s intersecting families in ([n]k) has size at most (nk)−(n−sk) for all sufficiently large n that satisfy n>(2+ϵ)k2+s with ϵ>0. We provide an example that shows that this result is essentially tight for the number of colors close to χ(KGn,k)=n−2k+2. We also improve the result of Bulankina and Kupavskii on the choice chromatic number, showing that it is at least 125nlogn for all k
AB - In this paper, we investigate two questions on Kneser graphs KGn,k. First, we prove that the union of s intersecting families in ([n]k) has size at most (nk)−(n−sk) for all sufficiently large n that satisfy n>(2+ϵ)k2+s with ϵ>0. We provide an example that shows that this result is essentially tight for the number of colors close to χ(KGn,k)=n−2k+2. We also improve the result of Bulankina and Kupavskii on the choice chromatic number, showing that it is at least 125nlogn for all k
KW - Choice chromatic number
KW - Erdos-Ko-Rado theorem
KW - Kneser graphs
UR - https://www.mendeley.com/catalogue/6611d1e3-e591-3fbd-90bb-0785f36dd17d/
U2 - 10.1016/j.disc.2025.114842
DO - 10.1016/j.disc.2025.114842
M3 - статья
VL - 349
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 2
ER -
ID: 151900208