کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423434 1342375 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hadwiger's Conjecture and inflations of the Petersen graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Hadwiger's Conjecture and inflations of the Petersen graph
چکیده انگلیسی

An inflation of a graph G is obtained by replacing vertices in G by disjoint cliques and adding all possible edges between any pair of cliques corresponding to adjacent vertices in G. We prove that the chromatic number of an arbitrary inflation F of the Petersen graph is equal to the chromatic number of some inflated 5-cycle contained in F. As a corollary, we find that Hadwiger's Conjecture holds for any inflation of the Petersen graph. This solves a problem posed by Bjarne Toft.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 24, 28 December 2012, Pages 3537-3543
نویسندگان
,