کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647925 1342383 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dense uniform hypergraphs have high list chromatic number
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Dense uniform hypergraphs have high list chromatic number
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 14, 28 July 2012, Pages 2119–2125
نویسندگان
, ,