Maximum face-constrained coloring of plane graphs

AbstractLet 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, then 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