On 3-coloring of plane triangulations
Atsuhiro Nakamoto, Katsuhiro Ota, Mamoru Watanabe · Ars Combinatoria · 2005
Let G be a plane triangulation. For a color-assignment λ : V (G) → {1, 2, 3}, a face of G whose vertices receive all three colors is called a vivid face with respect to λ. Let hλ(G) be the number of vivid faces in G with respect to λ. Let C(G) be the set of 3-color-assignments of G and let G(n) be the set of plane triangulations with n faces. Let h(G) = max{hλ(G) : λ ∈ C(G)} and h(n) = min{h(G)|G ∈ G(n)}. In this paper we show that h(n) ≥ 1 2n for any even n, and that h(n) ≤ 15(3n− 2) for infinitely many n.