共 50 条
Trivial colors in colorings of Kneser graphs
被引:0
|作者:
Kiselev, Sergei
[1
]
Kupavskii, Andrey
[1
,2
]
机构:
[1] Moscow Inst Phys & Technol, Moscow, Russia
[2] St Petersburg State Univ, St Petersburg, Russia
基金:
俄罗斯科学基金会;
关键词:
Kneser graphs;
Kneser colorings;
Non -trivial intersecting families;
INTERSECTION-THEOREMS;
CHROMATIC NUMBER;
CONJECTURE;
SYSTEMS;
D O I:
10.1016/j.disc.2023.113869
中图分类号:
O1 [数学];
学科分类号:
0701 ;
070101 ;
摘要:
We show that any proper coloring of a Kneser graph KG(n,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+epsilon)k(2), where epsilon -> 0 as k ->infinity. 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 KG(n,k).
引用
收藏
页数:7
相关论文