کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649608 1342461 2009 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Adaptable choosability of planar graphs with sparse short cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Adaptable choosability of planar graphs with sparse short cycles
چکیده انگلیسی

Given a (possibly improper) edge colouring FF of a graph GG, a vertex colouring of GG is adapted to  FF if no colour appears at the same time on an edge and on its two endpoints. A graph GG is called adaptablyk-choosable (for some positive integer kk) if for any list assignment LL to the vertices of GG, with |L(v)|≥k|L(v)|≥k for all vv, and any edge colouring FF of GG, GG admits a colouring cc adapted to FF where c(v)∈L(v)c(v)∈L(v) for all vv. This paper proves that a planar graph GG is adaptably 3-choosable if any two triangles in GG have distance at least 2 and no triangle is adjacent to a 4-cycle.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 20, 28 October 2009, Pages 6044–6047
نویسندگان
, ,