Cyclic Coloration of 3-Polytopes

摘要

In this paper, all graphs will be finite, loopless and will have no parallel lines. Let G be a 2-connected planar graph with =p points. Suppose G has some fixed imbedding Phi: G approaches R-sq in the plane. The pair (G Phi) is often called a plane graph. A cyclic coloration of (G Phi) is an assignment to colors to the points of G such that for any face-bounding cycle F of (G Phi), the points of F have different colors. The cyclic coloration number chi sub c ((G Phi)) is the minimum number of colors in any cyclic coloration of (G, Phi). The main result of the present paper is to show that if (G, Phi) is a 3-connected plane graph, then chi sub c (G, Phi) < p* (G, Phi)+ 9. Moreover, if rho* is sufficiently large of sufficiently large or sufficiently small, then this bound on chi sub c can be improved somewhat.