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
相关论文
共 50 条
  • [21] k-tuple colorings of the Cartesian product of graphs
    Bonomo, Flavia
    Koch, Ivo
    Torres, Pablo
    Valencia-Pabon, Mario
    DISCRETE APPLIED MATHEMATICS, 2018, 245 : 177 - 182
  • [22] On the chromatic number of two generalized Kneser graphs
    D'haeseleer, Jozefien
    Metsch, Klaus
    Werner, Daniel
    EUROPEAN JOURNAL OF COMBINATORICS, 2022, 101
  • [23] Clique number of Xor products of Kneser graphs
    Imolay, Andras
    Kocsis, Anett
    Schweitzer, Adam
    DISCRETE MATHEMATICS, 2022, 345 (07)
  • [24] On total and edge coloring some Kneser graphs
    de Figueiredo, C. M. H.
    Patrao, C. S. R.
    Sasaki, D.
    Valencia-Pabon, M.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (01) : 119 - 135
  • [25] Grundy domination and zero forcing in Kneser graphs
    Bresar, Bostjan
    Kos, Tim
    Daniel Tones, Pablo
    ARS MATHEMATICA CONTEMPORANEA, 2019, 17 (02) : 419 - 430
  • [26] On the boxicity of Kneser graphs and complements of line graphs
    Caoduro, Marco
    Lichev, Lyuben
    DISCRETE MATHEMATICS, 2023, 346 (05)
  • [27] L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs
    Shao, Zhendong
    Averbakh, Igor
    Solis-Oba, Roberto
    DISCRETE APPLIED MATHEMATICS, 2017, 221 : 106 - 114
  • [28] Achromatic numbers of Kneser graphs
    Araujo-Pardo, Gabriela
    Carlos Diaz-Patino, Juan
    Rubio-Montiel, Christian
    ARS MATHEMATICA CONTEMPORANEA, 2021, 21 (01)
  • [29] Random Kneser graphs and hypergraphs
    Kupavskii, Andrey
    ELECTRONIC JOURNAL OF COMBINATORICS, 2018, 25 (04)
  • [30] Treewidth of the generalized Kneser graphs
    Liu, Ke
    Cao, Mengyu
    Lu, Mei
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (01)