کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648185 1342397 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Acyclic 4-choosability of planar graphs without adjacent short cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Acyclic 4-choosability of planar graphs without adjacent short cycles
چکیده انگلیسی
There exist planar acyclically non-4-colorable bipartite graphs (Kostochka and Mel'nikov, 1976 [25]). This partly explains the fact that in all previously known sufficient conditions for the acyclic 4-choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles; namely, it is proved that a planar graph is acyclically 4-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3≤j≤6 if i=3 and 4≤j≤7 if i=4. In particular, this absorbs all the above-mentioned results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 22, 28 November 2012, Pages 3335-3341
نویسندگان
, ,