×

A new bound on the cyclic chromatic number. (English) Zbl 1027.05044

Summary: In 1969, Ore and Plummer defined an angular coloring as a natural extension of the four color problem: a face coloring of a plane graph where faces meeting even at a vertex must have distinct colors. A natural lower bound is the maximum degree \(\Delta\) of the graph. Some graphs require \(\lfloor{3\over 2}\Delta\rfloor\) colors in an angular coloring. Ore and Plummer gave an upper bound of \(2\Delta\), which was improved to \(\lfloor{9\over 3}\Delta\rfloor\) by the authors with Borodin. This article gives a new upper bound of \(\lceil{5\over 9}\Delta\rceil\) on the angular chromatic number. The cyclic chromatic number is the equivalent dual vertex coloring problem.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Appel, K.; Haken, W., Every planar map is four colorable: Part 1, Discharging, Illinois J. Math, 21, 429-490 (1977) · Zbl 0387.05009
[2] Borodin, O. V., Solution of Ringel’s problem on vertex-face coloring of plane graphs and coloring of 1-planar graphs, Metody Diskret. Analiz., 41, 12-26 (1984) · Zbl 0565.05027
[3] Borodin, O. V.; Sanders, D. P.; Zhao, Y., Cyclic colorings and their generalizations, Discrete Math., 203, 23-40 (1999) · Zbl 0929.05027
[4] Jensen, T. R.; Toft, B., Graph Coloring Problems (1995), Wiley: Wiley New York, p. 37-38
[5] Ore, O.; Plummer, M. D., Cyclic coloration of plane graphs, Recent Progress in Combinatorics, Proceedings of the Third Waterloo Conference on Combinatorics (1969), Academic Press: Academic Press San Diego, p. 287-293 · Zbl 0195.25701
[6] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R., The four-colour theorem, J. Combin. Theory Ser. B, 70, 2-44 (1997) · Zbl 0883.05056
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.