On the cyclic coloring conjecture

Abstract A cyclic coloring of a plane graph G is a coloring of its vertices such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a plane graph G is its cyclic chromatic number χ c ( G ) . Let Δ ∗ ( G ) be the maximum face degree of a graph G . In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph G has χ c ( G ) ≤ ⌊ 3 2 Δ ∗ ( G ) ⌋ , it is enough to do it for subdivisions of simple 3-connected plane graphs. We have discovered four new different upper bounds on χ c ( G ) for graphs G from this restricted family; three bounds of them are tight. As corollaries, we have shown that the conjecture holds for subdivisions of plane triangulations, simple 3-connected plane quadrangulations, and simple 3-connected plane pentagulations with an even maximum face degree, for regular subdivisions of simple 3-connected plane graphs of maximum degree at least 10, and for subdivisions of simple 3-connected plane graphs having the maximum face degree large enough in comparison with the number of vertices of their longest paths consisting only of vertices of degree two.