Premium
Coloring uniform hypergraphs with few colors
Author(s) -
Kostochka Alexandr
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10109
Subject(s) - hypergraph , combinatorics , mathematics , struct , upper and lower bounds , discrete mathematics , computer science , mathematical analysis , programming language
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) . © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004