Cyclic coloring of plane graphs
type: Item
instance of: scholarly article
title: Cyclic coloring of plane graphs
zbMATH Open document ID: 0765.05044
DOI: 10.1016/0012-365X(92)90647-X
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: Let \(G\) be a plane graph, and let \(x_ k(G)\) be the minimum number of colors to color the vertices of \(G\) so that every two of them which lie in the boundary of the same face of the size at most \(k\), receive different colors. \textit{O. Ore} and \textit{M. D. Plummer} [Recent Progress Combin., Proc. 3rd Waterloo Conf. 1968, 287-293 (1969; Zbl 0195.257)] proved that \(x_ k(G)\leq 2k\) for any \(k\geq 3\). It is also known that \(x_ 3(G)\leq 4\) (\textit{K. Appel} and \textit{W. Haken}, 1976) and \(x_ 4(G)\leq 6\) (\textit{O. V. Borodin}, 1984). Let the function \(q(k)\) be defined as follows: \(q(5)=9\), \(q(6)=11\), \(q(7)=12\), and \(q(k)=2k-3\) for \(k\geq 8\). In this paper it is proved that if \(G\) is a connected plane graph, then \(x_ k(G)\leq q(k)\) for all \(k\geq 5\) and \(\max_ Gx_ k(G)\geq\lfloor 3k/2\rfloor\). The order of magnitude of \(\max_ Gx_ k(G)\) for large \(k\) is not known.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 90264
zbMATH Keywords: cyclic coloring
zbMATH Keywords: edge-transmitter
zbMATH Keywords: \(k\)-cyclic chromatic number
zbMATH Keywords: color
zbMATH Keywords: boundary
zbMATH Keywords: face
zbMATH Keywords: plane graph
author: Oleg V. Borodin
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: The existence of unavoidable sets of geographically good configurations
cites work: Q3679212
cites work: Q5591378
cites work: Cyclic coloration of 3-polytopes
cites work: Ein Sechsfarbenproblem auf der Kugel
full work available at URL: 0012-365x(92)90647-x
OpenAlex ID: W2044384336
description: scientific article; zbMATH DE number 90264