Standard

Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs. / Balogh, József; Cherkashin, Danila; Kiselev, Sergei.

In: European Journal of Combinatorics, Vol. 79, 01.06.2019, p. 228-236.

Research output: Contribution to journal › Article › peer-review

Harvard

Balogh, J, Cherkashin, D & Kiselev, S 2019, 'Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs', European Journal of Combinatorics, vol. 79, pp. 228-236. https://doi.org/10.1016/j.ejc.2019.03.004

APA

Balogh, J., Cherkashin, D., & Kiselev, S. (2019). Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs. European Journal of Combinatorics, 79, 228-236. https://doi.org/10.1016/j.ejc.2019.03.004

Vancouver

Balogh J, Cherkashin D, Kiselev S. Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs. European Journal of Combinatorics. 2019 Jun 1;79:228-236. https://doi.org/10.1016/j.ejc.2019.03.004

Author

Balogh, József ; Cherkashin, Danila ; Kiselev, Sergei. / Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs. In: European Journal of Combinatorics. 2019 ; Vol. 79. pp. 228-236.

BibTeX

@article{25cc3ffe20ca41a4a9b8e660e502c22c,
title = "Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs",
abstract = " 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. ",
keywords = "CHROMATIC NUMBER, DIAMETER, THEOREMS",
author = "J{\'o}zsef Balogh and Danila Cherkashin and Sergei Kiselev",
year = "2019",
month = jun,
day = "1",
doi = "10.1016/j.ejc.2019.03.004",
language = "English",
volume = "79",
pages = "228--236",
journal = "European Journal of Combinatorics",
issn = "0195-6698",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs

AU - Balogh, József

AU - Cherkashin, Danila

AU - Kiselev, Sergei

PY - 2019/6/1

Y1 - 2019/6/1

N2 - 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.

AB - 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.

KW - CHROMATIC NUMBER

KW - DIAMETER

KW - THEOREMS

UR - http://www.scopus.com/inward/record.url?scp=85064090237&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/coloring-general-kneser-graphs-hypergraphs-via-highdiscrepancy-hypergraphs

U2 - 10.1016/j.ejc.2019.03.004

DO - 10.1016/j.ejc.2019.03.004

M3 - Article

AN - SCOPUS:85064090237

VL - 79

SP - 228

EP - 236

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -

ID: 41133039