首页 | 本学科首页   官方微博 | 高级检索  
     


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 d is at least (0.5?o(1))log2d. We prove that for r3, every r-uniform hypergraph in which at least half of the (r?1)-vertex subsets are contained in at least d edges has list chromatic number at least lnd100r3. When r is fixed, this is sharp up to a constant factor.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号