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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom