کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651350 1632450 2006 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
List colourings of planar graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
List colourings of planar graphs
چکیده انگلیسی

A graph G=G(V,E)G=G(V,E) is called L-list colourable if there is a vertex colouring of G   in which the colour assigned to a vertex vv is chosen from a list L(v)L(v) associated with this vertex. We say G   is kk-choosable   if all lists L(v)L(v) have the cardinality k and G is L-list colourable for all possible assignments of such lists. There are two classical conjectures from Erdős, Rubin and Taylor 1979 about the choosability of planar graphs:(1)every planar graph is 5-choosable and,(2)there are planar graphs which are not 4-choosable.We will prove the second conjecture.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 10–11, 28 May 2006, Pages 1076–1079
نویسندگان
,