کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872465 | 681651 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On (3,1)â-choosability of planar graphs without adjacent short cycles
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
There exist planar graphs containing 4-cycles that are not (3,1)â-choosable (Cowen et al., 1986 [1]). This partly explains the fact that in all above known sufficient conditions for the (3,1)â-choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles. More precisely, we prove that every planar graph without 4-cycles adjacent to 3- and 4-cycles is (3,1)â-choosable. This is a common strengthening of all above mentioned results. Moreover as a consequence we give a partial answer to a question of Xu and Zhang (2007) [11] and show that every planar graph without 4-cycles is (3,1)â-choosable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 159-166
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 159-166
نویسندگان
Min Chen, André Raspaud,