کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421453 684471 2007 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Every toroidal graph without adjacent triangles is (4,1)*(4,1)*-choosable
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Every toroidal graph without adjacent triangles is (4,1)*(4,1)*-choosable
چکیده انگلیسی

In this paper, a structural theorem about toroidal graphs is given that strengthens a result of Borodin on plane graphs. As a consequence, it is proved that every toroidal graph without adjacent triangles is (4,1)*(4,1)*-choosable. This result is best possible in the sense that K7K7 is a non-(3,1)*(3,1)*-choosable toroidal graph. A linear time algorithm for producing such a coloring is presented also.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 1, 1 January 2007, Pages 74–78
نویسندگان
, ,