On \(3\)-Coloring of Plane Triangulations

Atsuhiro Nakamoto1, Katsuhiro Ota2, Mamoru Watanabe3
1Department of Mathematics Osaka Kyouiku University, Japan
2Department of Mathematics Keio University, Japan
3Department of Computer Science and Mathematics Kurashiki University of Science and the Arts, Japan

Abstract

For a \(3\)-vertex coloring, a face of a triangulation whose vertices receive all three colors is called a vivid face with respect to it. In this paper, we show that for any triangulation \(G\) with \(n\) faces, there exists a coloring of \(G\) with at least \( \frac{1}{2}n\) faces and construct an infinite series of plane triangulations such that any \(3\)-coloring admits at most \(\frac{1}{5}(3n- 2)\) vivid faces.