The cyclic chromatic number of a plane graph G is the smallest number chi(C)(G) of colors that can be assigned to vertices of G in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer and Toft in 1987 that, for every 3-connected plane graph G, chi(C)(G) <= Delta*(G)+2, where Delta*(G) is the maximum face degree of G. The best upper bound known so far was Delta*(G)+8. In the paper this bound is improved to Delta*(G)+5.
展开▼
