کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777092 1632570 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the List Coloring Version of Reed's Conjecture
ترجمه فارسی عنوان
در لیست نسخه رنگی گزاره رید
کلمات کلیدی
رنگ آمیزی نمودار، فهرست رنگ آمیزی، تئوری رید،
ترجمه چکیده
طبیعتا تعجب می کنم که آیا نتایج مشابهی برای لیست رنگی لیست وجود دارد. متاسفانه، تکنیک های قبلی برای رنگ آمیزی معمولی به رنگ لیست نمی روند. در این مقاله، با معرفی چند ایده جدید، بر این موانع غلبه می کنیم. نتیجه اصلی ما این است که تعداد کروماتیک لیست، بیشترین تعداد ترکیبی از محدب غیرمعمول تعداد کل و حداکثر درجه به علاوه یک است. علاوه بر این، ما نشان می دهد که برای حداکثر به اندازه کافی بزرگ، که ترکیبی از 1/13 کافی است. توجه داشته باشید که این نیز در بهترین نتایج شناخته شده برای رنگ آمیزی معمولی را بهبود می بخشد.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش مقاله
در لیست نسخه رنگی گزاره رید
چکیده انگلیسی
It is natural to wonder if similar results hold for the list chromatic number. Unfortunately, previous techniques for ordinary coloring do not extend to list coloring. In this paper, we overcome these hurdles by introducing several new ideas. Our main result is that the list chromatic number is at most some non-trivial convex combination of the clique number and the maximum degree plus one. Furthermore, we show that for large enough maximum degree, that a combination of 1/13 suffices. Note that this also improves on the best known results for ordinary coloring.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 343-349
نویسندگان
, ,