Cyclic Coloration of 3-Polytopes,
Abstract
This paper, all graphs will be finite, loopless and will have no parallel lines. Let G be a 2-connected planar graph with <V(G)>=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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1985
- Accession Number
- ADA175241
Entities
People
- Bjarne Toft
- Michael D. Plummer
Organizations
- Vanderbilt University