Cyclic coloring of plane graphs (Q1198649)

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.