On maximum face-constrained coloring of plane graphs with no short face cycles. (Q1426126): Difference between revisions

A face of a plane graph is said to be polychromatic if all its vertices receive mutually different colors. In this paper it is shown that the vertices of each plane graph \(G\) of order \(n\) can be colored in such a way that \(G\) does not contain a polychromatic face using at least: \(n-m\) colors if the dual graph \(G^{*}\) of \(G\) has a covering with \(m\) edges; \(\lceil n/2\rceil +1\) if all face cycles have lengths at least five and \(n\geq 4\); \(\lceil (g^{2}-g-8)n/(g^{2}+g-6)+(4g+4)/(g^{2}+g-6)\rceil \) if all face cycles have lengths at least \(g\), \(g\geq 5\) and \(n\geq (g+3)/2\).