کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651873 1632582 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Third case of the Cyclic Coloring Conjecture
ترجمه فارسی عنوان
مورد سوم از گزاره رنگ آمیزی چرخه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

The Cyclic Coloring Conjecture of Ore and Plummer from 1969 asserts that the vertices of every plane graph with maximum face size Δ⁎ can be colored using at most ⌊3Δ⁎/2⌋ colors in such a way that no face is incident with two vertices of the same color. The Cyclic Coloring Conjecture has been proven only for two values of Δ⁎: the case Δ⁎=3 is equivalent to the Four Color Theorem and the case Δ⁎=4 is equivalent to Borodin's Six Color Theorem, which says that every graph that can be drawn in the plane with each edge crossed by at most one other edge is 6-colorable. We prove the case Δ⁎=6 of the conjecture.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 11-15