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 条
  • [1] Injective colorings of planar graphs with few colors
    Luzar, Borut
    Skrekovski, Riste
    Tancer, Martin
    DISCRETE MATHEMATICS, 2009, 309 (18) : 5636 - 5649
  • [2] A Generalization of Kneser Graphs
    Bobu, A., V
    Kupriyanov, A. E.
    Raigorodskii, A. M.
    MATHEMATICAL NOTES, 2020, 107 (3-4) : 392 - 403
  • [3] On the number of star-shaped classes in optimal colorings of Kneser graphs
    Daneshpajouh, Hamid Reza
    JOURNAL OF GRAPH THEORY, 2024, 105 (02) : 230 - 238
  • [4] Maximal Degrees in Subgraphs of Kneser Graphs
    Frankl, Peter
    Kupavskii, Andrey
    JOURNAL OF GRAPH THEORY, 2025, 109 (01) : 88 - 96
  • [5] The toughness of Kneser graphs
    Park, Davin
    Ostuni, Anthony
    Hayes, Nathan
    Banerjee, Amartya
    Wakhare, Tanay
    Wong, Wiseley
    Cioaba, Sebastian
    DISCRETE MATHEMATICS, 2021, 344 (09)
  • [6] On the general position problem on Kneser graphs
    Patkos, Balazs
    ARS MATHEMATICA CONTEMPORANEA, 2020, 18 (02) : 273 - 280
  • [7] A new coloring theorem of Kneser graphs
    Chen, Peng-An
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2011, 118 (03) : 1062 - 1071
  • [8] Choice number of Kneser graphs
    Bulankina, Vera
    Kupavskii, Andrey
    DISCRETE MATHEMATICS, 2022, 345 (11)
  • [9] Sharp bounds for the chromatic number of random Kneser graphs
    Kiselev, Sergei
    Kupavskii, Andrey
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, 157 : 96 - 122
  • [10] A combinatorial proof for the circular chromatic number of Kneser graphs
    Liu, Daphne Der-Fen
    Zhu, Xuding
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (03) : 765 - 774