کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648168 | 1342395 | 2011 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
List precoloring extension in planar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen’s theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a “wide” Steiner tree containing all the precolored vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 12, 28 June 2011, Pages 1046–1056
Journal: Discrete Mathematics - Volume 311, Issue 12, 28 June 2011, Pages 1046–1056
نویسندگان
Maria Axenovich, Joan P. Hutchinson, Michelle A. Lastrina,