Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
复制标题
通过高差异超图对通用 Kneser 图和超图进行着色
DOI：
10.1016/j.ejc.2019.03.004
复制
发表时间：
2019
影响因子：
1
通讯作者：
Kiselev, Sergei
中科院分区：
文献类型：
--
作者：
Balogh, József;Cherkashin, Danila;Kiselev, Sergei
提出了一种基于高差异度、边数少的超图的广义Kneser图着色的新方法。主要结果给出了K（n，nscin2 − t，s）在（4+ o（1））（s+ t）2色中的一个适当着色，它是由Hadamard矩阵产生的.此外，我们表明，着色的自然类型的独立集，这个结果是最好的可能的乘法常数。我们的方法扩展到Kneser超图以及。
We suggest a new method for coloring generalized Kneser graphs based on hypergraphs with high discrepancy and a small number of edges. The main result provides a proper coloring of K (n, n∕ 2− t, s) in (4+ o (1))(s+ t) 2 colors, which is produced by Hadamard matrices. Also, we show that for colorings by independent set of a natural type, this result is the best possible up to a multiplicative constant. Our method extends to Kneser hypergraphs as well.
登录
查看更多内容
具有组合证明的广义 Kneser 着色定理
影响因子：
3.1
作者：
G. Ziegler
通讯作者：
G. Ziegler
DOI：
10.1002/jgt.3190090204
发表时间：
1985
期刊：
J. Graph Theory
影响因子：
--
作者：
P. Frankl
通讯作者：
P. Frankl
影响因子：
1.3
作者：
D. Kozlov
通讯作者：
D. Kozlov
影响因子：
1.2
作者：
A. Bobu;A. Kupriyanov
通讯作者：
A. Kupriyanov
没有对映体对的载体家族
DOI：
10.1556/012.2018.55.2.1394
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
P. Frankl;A. Kupavskii
通讯作者：
A. Kupavskii