On the number of star-shaped classes in optimal colorings of Kneser graphs

被引：0
|
作者：
Daneshpajouh, Hamid Reza [1 ,2 ]
机构：
[1] Univ Nottingham Ningbo China, Sch Math Sci, Ningbo, Peoples R China
[2] Univ Nottingham Ningbo China, Sch Math Sci, 199 Taikang East Rd, Ningbo 315100, Peoples R China
来源：
JOURNAL OF GRAPH THEORY | 2024年 / 105卷 / 02期
关键词：
chromatic number; Kneser graph; line graph; CHROMATIC NUMBER; PROOF;
D O I：
10.1002/jgt.23032
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A family of sets is called star-shaped if all the members of the family have a point in common. The main aim of this paper is to provide a negative answer to the following question raised by Aisenberg et al., for the case k=2 $k=2$. Do there exist (n-2k+2) $(n-2k+2)$-colorings of the (n,k) $(n,k)$-Kneser graphs with more than k-1 $k-1$ many non-star-shaped color classes?
引用
收藏
页码：230 / 238
页数：9
相关论文
共 31 条
  • [1] Trivial colors in colorings of Kneser graphs
    Kiselev, Sergei
    Kupavskii, Andrey
    DISCRETE MATHEMATICS, 2024, 347 (04)
  • [2] The equitable colorings of Kneser graphs
    Chen, Bor-Liang
    Huang, Kuo-Ching
    TAIWANESE JOURNAL OF MATHEMATICS, 2008, 12 (04): : 887 - 900
  • [3] Choice number of Kneser graphs
    Bulankina, Vera
    Kupavskii, Andrey
    DISCRETE MATHEMATICS, 2022, 345 (11)
  • [4] A NOTE ON FALL COLORINGS OF KNESER GRAPHS
    Shaebani, Saeed
    TRANSACTIONS ON COMBINATORICS, 2019, 8 (03) : 13 - +
  • [5] OPTIMAL REAL NUMBER GRAPH LABELLINGS OF A SUBFAMILY OF KNESER GRAPHS
    Erman, Rok
    Jurecic, Suzana
    Kral', Daniel
    Stopar, Kris
    Stopar, Nik
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) : 1372 - 1381
  • [6] Strong edge colorings of graphs and the covers of Kneser graphs
    Luzar, Borut
    Macajova, Edita
    Skoviera, Martin
    Sotak, Roman
    JOURNAL OF GRAPH THEORY, 2022, 100 (04) : 686 - 697
  • [7] Circular chromatic number of induced subgraphs of Kneser graphs
    Alishahi, Meysam
    Taherkhani, Ali
    ARS MATHEMATICA CONTEMPORANEA, 2018, 15 (01) : 161 - 172
  • [8] ON THE CHROMATIC NUMBER OF GENERALIZED KNESER GRAPHS
    Jafari, Amir
    Alipour, Sharareh
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2017, 12 (02) : 69 - 76
  • [9] The determining number of Kneser graphs
    Caceres, Jose
    Garijo, Delia
    Gonzalez, Antonio
    Marquez, Alberto
    Luiz Puertas, Maria
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2013, 15 (01): : 1 - 14
  • [10] On the chromatic number of q-Kneser graphs
    A. Blokhuis
    A. E. Brouwer
    T. Szőnyi
    Designs, Codes and Cryptography, 2012, 65 : 187 - 197
1234