کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777579 | 1632966 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Coloring graphs with forbidden minors
ترجمه فارسی عنوان
نمودار های رنگ آمیزی با افراد غیر مجاز
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حدس هادیفر، نمودار جزئی نمودار بحران کنترلی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Hadwiger's conjecture from 1943 states that for every integer tâ¥1, every graph either can be t-colored or has a subgraph that can be contracted to the complete graph on t+1 vertices. As pointed out by Paul Seymour in his recent survey on Hadwiger's conjecture, proving that graphs with no K7 minor are 6-colorable is the first case of Hadwiger's conjecture that is still open. It is not known yet whether graphs with no K7 minor are 7-colorable. Using a Kempe-chain argument along with the fact that an induced path on three vertices is dominating in a graph with independence number two, we first give a very short and computer-free proof of a recent result of Albar and Gonçalves and generalize it to the next step by showing that every graph with no Kt minor is (2tâ6)-colorable, where tâ{7,8,9}. We then prove that graphs with no K8â minor are 9-colorable, and graphs with no K8= minor are 8-colorable. Finally we prove that if Mader's bound for the extremal function for Kt minors is true, then every graph with no Kt minor is (2tâ6)-colorable for all tâ¥6. This implies our first result. We believe that the Kempe-chain method we have developed in this paper is of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 127, November 2017, Pages 14-31
Journal: Journal of Combinatorial Theory, Series B - Volume 127, November 2017, Pages 14-31
نویسندگان
Martin Rolek, Zi-Xia Song,