کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657092 1343714 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
چکیده انگلیسی

It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable [O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B 93 (2005) 303–311]. We improve this result by proving that every planar graph without 5- and 7-cycles and without adjacent triangles is 3-colorable. Also, we give counterexamples to the proof of the same result in [B. Xu, On 3-colorable plane graphs without 5- and 7-cycles, J. Combin. Theory Ser. B 96 (2006) 958–963].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 99, Issue 4, July 2009, Pages 668-673