Unique-maximum coloring of plane graphs

Abstract

A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . . , k so that, for each face of G, the maximum color occurs exactly once on the vertices of . We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.