Informace o publikaci
THIRD CASE OF THE CYCLIC COLORING CONJECTURE
| Autoři | |
|---|---|
| Rok publikování | 2016 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1137/15M1019490 |
| Klíčová slova | cyclic coloring; planar graphs |
| Popis | 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. |