Article ID Journal Published Year Pages File Type
4651873 Electronic Notes in Discrete Mathematics 2015 5 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics