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.

Keywords

• plane graph
• weak-parity coloring
• unique-maximum coloring
• 05c15