Article ID Journal Published Year Pages File Type
4647925 Discrete Mathematics 2012 7 Pages PDF
Abstract

The first author showed that the list chromatic number of every graph with average degree dd is at least (0.5−o(1))log2d(0.5−o(1))log2d. We prove that for r≥3r≥3, every rr-uniform hypergraph in which at least half of the (r−1)(r−1)-vertex subsets are contained in at least dd edges has list chromatic number at least lnd100r3. When rr is fixed, this is sharp up to a constant factor.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,