×

Cyclic coloration of 3-polytopes. (English) Zbl 0655.05030

The 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

Citations:

Zbl 0195.257
PDFBibTeX XMLCite
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.