Coloring Uniform Hypergraphs with Few Colors

Alexandr Kostochka

doi:10.1002/rsa.10109

Coloring Uniform Hypergraphs with Few Colors

Alexandr Kostochka

Mathematics

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

Abstract

Let m(r, k) denote the minimum number of edges in an r-uniform hypergraph that is not k-colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2 ⁿ, then m(r, k) ≥ ε(k)k ^r (r/ln r) ^n/(n+1).

Original language	English (US)
Pages (from-to)	1-10
Number of pages	10
Journal	Random Structures and Algorithms
Volume	24
Issue number	1
DOIs	https://doi.org/10.1002/rsa.10109
State	Published - Jan 2004

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Online availability

10.1002/rsa.10109

Library availability

Discover UIUC Full Text

Cite this

@article{b41808715ce849d283337dd1c06412cc,

title = "Coloring Uniform Hypergraphs with Few Colors",

abstract = "Let m(r, k) denote the minimum number of edges in an r-uniform hypergraph that is not k-colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2 n, then m(r, k) ≥ ε(k)k r (r/ln r) n/(n+1).",

author = "Alexandr Kostochka",

year = "2004",

month = jan,

doi = "10.1002/rsa.10109",

language = "English (US)",

volume = "24",

pages = "1--10",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley & Sons, Ltd.",

number = "1",

}

TY - JOUR

T1 - Coloring Uniform Hypergraphs with Few Colors

AU - Kostochka, Alexandr

PY - 2004/1

Y1 - 2004/1

N2 - Let m(r, k) denote the minimum number of edges in an r-uniform hypergraph that is not k-colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2 n, then m(r, k) ≥ ε(k)k r (r/ln r) n/(n+1).

AB - Let m(r, k) denote the minimum number of edges in an r-uniform hypergraph that is not k-colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2 n, then m(r, k) ≥ ε(k)k r (r/ln r) n/(n+1).

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

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

U2 - 10.1002/rsa.10109

DO - 10.1002/rsa.10109

M3 - Article

AN - SCOPUS:0346938371

SN - 1042-9832

VL - 24

SP - 1

EP - 10

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

Coloring Uniform Hypergraphs with Few Colors

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this