Maximum Face-Constrained Coloring of Plane Graphs

Let f(G) be the maximum number of colors in a vertex coloring of a simple plane graph G such that no face has distinct colors on all its vertices. If G has n vertices and chromatic number k, f(G) ≥ ⌈ n/k ⌉ + 1. For k ∈ {2, 3}, this bound is sharp for all n (except n ≤ 3 when k = 2). For k = 4, the bound is within 1 for all n.