Publication details
THIRD CASE OF THE CYCLIC COLORING CONJECTURE
| Authors | |
|---|---|
| Year of publication | 2016 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1137/15M1019490 |
| Keywords | cyclic coloring; planar graphs |
| Description | The Cyclic Coloring Conjecture asserts that the vertices of every plane graph with maximum face size Delta* can be colored using at most left perpendicular3 Delta*/2right perpendicular 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 Delta*: the case Delta* = 3 is equivalent to the Four Color Theorem and the case Delta* = 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 Delta* = 6 of the conjecture. |