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

来源：

DISCRETE MATHEMATICS | 2024年 / 347卷 / 04期

基金：

俄罗斯科学基金会;

关键词：

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 条

[41] A Kruskal-Katona-type theorem for graphs: q-Kneser graphs
Wang, Jun
Xu, Ao
Zhang, Huajun
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2023, 198
[42] Graphs whose Kronecker covers are bipartite Kneser graphs
Matsushita, Takahiro
DISCRETE MATHEMATICS, 2021, 344 (04)
[43] THE SUPER-CONNECTIVITY OF KNESER GRAPHS
Ekinci, Gulnaz Boruzanli
Gauci, John Baptist
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) : 5 - 11
[44] On b-coloring of the Kneser graphs
Javadi, Ramin
Omoomi, Behnaz
DISCRETE MATHEMATICS, 2009, 309 (13) : 4399 - 4408
[45] Cyclic colorings of plane graphs with independent faces
Azarija, Jernej
Erman, Rok
Kral, Daniel
Krnc, Matjaz
Stacho, Ladislav
EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (03) : 294 - 301
[46] Gromov hyperbolicity of Johnson and Kneser graphs
Mendez, Jesus
Reyes, Rosalio
Rodriguez, Jose M.
Sigarreta, Jose M.
AEQUATIONES MATHEMATICAE, 2024, 98 (03) : 661 - 686
[47] b-coloring of Kneser graphs
Balakrishnan, R.
Kavaskar, T.
DISCRETE APPLIED MATHEMATICS, 2012, 160 (1-2) : 9 - 14
[48] On finite simple groups and Kneser graphs
Andrea Lucchini
Attila Maróti
Journal of Algebraic Combinatorics, 2009, 30 : 549 - 566
[49] COUNTEREXAMPLES TO A CONJECTURE ON MATCHING KNESER GRAPHS
Iradmusa, Moharram N.
TRANSACTIONS ON COMBINATORICS, 2023, 12 (03) : 172 - 173
[50] The equivariant topology of stable Kneser graphs
Schultz, Carsten
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2011, 118 (08) : 2291 - 2318

← 1 2 3 4 5 →