کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649296 1342449 2006 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bordeaux 3-color conjecture and 3-choosability
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Bordeaux 3-color conjecture and 3-choosability
چکیده انگلیسی

A graph G=(V,E)G=(V,E) is list L  -colorable if for a given list assignment L={L(v):v∈V}L={L(v):v∈V}, there exists a proper coloring c of G   such that c(v)∈L(v)c(v)∈L(v) for all v∈Vv∈V. If G is list L  -colorable for every list assignment with |L(v)|⩾k|L(v)|⩾k for all v∈Vv∈V, then G is said to be k-choosable.In this paper, we prove that (1) every planar graph either without 4- and 5-cycles, and without triangles at distance less than 4, or without 4-, 5- and 6-cycles, and without triangles at distance less than 3 is 3-choosable; (2) there exists a non-3-choosable planar graph without 4-cycles, 5-cycles, and intersecting triangles. These results have some consequences on the Bordeaux 3-color conjecture by Borodin and Raspaud [A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B 88 (2003) 17–27].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 6, 6 April 2006, Pages 573–579
نویسندگان
, , ,