Cyclic coloration of 3-polytopes.

*(English)*Zbl 0655.05030The main results in the present paper are concerned with 3-connected planar graphs which are just the family of “3-polytopes” by a celebrated theorem of Steinitz. By a classical result due to Whitney there is essentially only one way to imbed them in the plane. A cyclic coloration of a planar graph G is an assignment of colors to the points of G such that for any face-bounding cycle F of G, the points of F have different colors. The cyclic coloration number \(\chi_ c(G)\) is the minimum number of colors in any cyclic coloration of G. The main result in this paper asserts that \(\chi_ c(G)\leq \rho\) \(*(G)+9\) for every 3- connected plane graph G with maximum face size \(\rho\) *(G), thus improving the upper bound \(2\rho\) *(G), due to O. Ore and the first author [Recent Prog. Comb., Proc. 3rd Waterloo Conf. 1968, 287-293 (1969; Zbl 0195.257)]. The proof uses two principal tools: the theory of Euler contributions and recent results on contractible lines in 3-connected graphs by K. Ando, H. Enomoto and A. Saito. If \(\rho\) *(G) is sufficiently small or suffuciently large, this bound can be improved.

Reviewer: I.Tomescu

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

##### Keywords:

planar graphs; 3-polytopes; cyclic coloration; cyclic coloration number; contractible lines
PDF
BibTeX
XML
Cite

\textit{M. D. Plummer} and \textit{B. Toft}, J. Graph Theory 11, No. 4, 507--515 (1987; Zbl 0655.05030)

Full Text:
DOI

##### References:

[1] | , and , Contractible edges in 3-connected graphs. Technical Report 85-03, Department of Information Science, University of Tokyo (1985). |

[2] | Appel, Illinois J. Math. 21 pp 429– (1977) |

[3] | Appel, Illinois J. Math. 21 pp 491– (1977) |

[4] | Borodin, Metody Diskret. Analiz. 41 pp 12– (1984) |

[5] | Consistent coloring of 1-imbeddable graphs. Graphen und Netzwerke–Theorie und Anwendungen, 30. Intern. Wiss. Koll. TH Ilmenau 1985, Ilmenau, D.D.R. (1985) 19–20 [Russian]. |

[6] | Convex Polytopes. Wiley Interscience, London, (1967). · Zbl 0163.16603 |

[7] | Graph Theory. Addison-Wesley, Reading, MA (1969). |

[8] | Lebesgue, J. de Math. 9 pp 27– (1940) |

[9] | and , Matching Theory, Ann. Discrete Math. 29, North-Holland, Amsterdam, and Akadémiai Kiadó, Budapest (1986). |

[10] | The Four-Color Problem. Academic Press, New York (1967). · Zbl 0149.21101 |

[11] | and , Cyclic coloration of plane graphs. Recent Progress in Combinatorics, Proceedings of the Third Waterloo Conference on Combinatorics, Academic Press, New York (1969) 287–293. |

[12] | A theorem on matchings in the plane. Conference in Memory of Gabriel Dirac, Ann. Discrete Math., North-Holland, Amsterdam (to appear). |

[13] | Steinitz, Enzykl. math. Wiss. 3 pp 12– (1922) |

[14] | Thomassen, J. Combin. Theory Ser. B 29 pp 244– (1980) |

[15] | Tutte, Proc. London Math. Soc. 13 pp 743– (1963) |

[16] | Graphs, Groups and Surfaces. North-Holland/American Elsevier, Amsterdam (1973). |

[17] | Whitney, Am. J. Math. 54 pp 150– (1932) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.