Colouring of plane graphs with unique maximal colours on faces

Alex Wendland

Published 2014-09-08Version 1

The Four Colour Theorem asserts that the vertices of every plane graph can be properly coloured with four colors. Fabrici and G\"{o}ring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly coloured with the numbers 1,...,4 in such a way that every face contains a unique vertex coloured with the maximal color appearing on that face. They proved that every plane graph has such a colouring with the numbers 1,...,6. We prove that every plane graph has such a colouring with the numbers 1,...,5 and we also prove the list variant of the statement for lists of sizes seven.