Dense uniform hypergraphs have high list chromatic number |
| |
Authors: | Noga Alon Alexandr Kostochka |
| |
Affiliation: | 1. Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel;2. Institute for Advanced Study, Princeton, NJ, 08540, USA;3. Department of Mathematics, University of Illinois, Urbana, IL, 61801, USA;4. Sobolev Institute of Mathematics, Novosibirsk, Russia |
| |
Abstract: | The first author showed that the list chromatic number of every graph with average degree is at least . We prove that for , every -uniform hypergraph in which at least half of the -vertex subsets are contained in at least edges has list chromatic number at least . When is fixed, this is sharp up to a constant factor. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|