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 条
  • [31] Geodetic convexity and kneser graphs
    Bedo, Marcos
    Leite, Joao V. S.
    Oliveira, Rodolfo A.
    Protti, Fabio
    APPLIED MATHEMATICS AND COMPUTATION, 2023, 449
  • [32] Symmetries of the stable Kneser graphs
    Braun, Benjamin
    ADVANCES IN APPLIED MATHEMATICS, 2010, 45 (01) : 12 - 14
  • [33] Local coloring of Kneser graphs
    Omoomi, Behnaz
    Pourmiri, Ali
    DISCRETE MATHEMATICS, 2008, 308 (24) : 5922 - 5927
  • [34] A combinatorial proof for the circular chromatic number of Kneser graphs
    Daphne Der-Fen Liu
    Xuding Zhu
    Journal of Combinatorial Optimization, 2016, 32 : 765 - 774
  • [35] Circular chromatic number of induced subgraphs of Kneser graphs
    Alishahi, Meysam
    Taherkhani, Ali
    ARS MATHEMATICA CONTEMPORANEA, 2018, 15 (01) : 161 - 172
  • [36] Hoffman colorings of graphs
    Abiad, Aida
    Bosma, Wieb
    van Veluw, Thijs
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2025, 710 : 129 - 150
  • [37] On dominator colorings in graphs
    Arumugam, S.
    Bagga, Jay
    Chandrasekar, K. Raja
    PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 2012, 122 (04): : 561 - 571
  • [38] On dominator colorings in graphs
    S ARUMUGAM
    JAY BAGGA
    K RAJA CHANDRASEKAR
    Proceedings - Mathematical Sciences, 2012, 122 : 561 - 571
  • [39] On the chromatic number of generalized Kneser graphs and Hadamard matrices
    Jafari, Amir
    Moghaddamzadeh, Mohammad Javad
    DISCRETE MATHEMATICS, 2020, 343 (02)
  • [40] SHARP BOUNDS FOR THE CHROMATIC NUMBER OF RANDOM KNESER GRAPHS
    Kiselev, S.
    Kupavskii, A.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 861 - 865