کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776917 | 1413645 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Double-critical graph conjecture for claw-free graphs
ترجمه فارسی عنوان
فرضیه گراف دوگانه برای گرافهای بدون نقص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی ورتکس، نمودارهای دو بحرانی، نمودارهای بدون چنگال،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A connected graph G with chromatic number t is double-critical if Gâ{x,y} is (tâ2)-colorable for each edge xyâE(G). The complete graphs are the only known examples of double-critical graphs. A long-standing conjecture of ErdÅs and Lovász from 1966, which is referred to as the Double-Critical Graph Conjecture, states that there are no other double-critical graphs. That is, if a graph G with chromatic number t is double-critical, then G is the complete graph on t vertices. This has been verified for tâ¤5, but remains open for tâ¥6. In this paper, we first prove that if G is a non-complete, double-critical graph with chromatic number tâ¥6, then no vertex of degree t+1 is adjacent to a vertex of degree t+1, t+2, or t+3 in G. We then use this result to show that the Double-Critical Graph Conjecture is true for double-critical graphs G with chromatic number tâ¤8 if G is claw-free.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1633-1638
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1633-1638
نویسندگان
Martin Rolek, Zi-Xia Song,