Riste Škrekovski: Some results on unique-maximum coloring of plane graphs

Povzetek. A unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face alpha the maximal color appears exactly once on the vertices of alpha. Fabrici and Göring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem.
Wendland later decreased the upper bound from six to five.

We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. So, we conclude that the facial unique-maximum chromatic number of the sphere is not four but five.

Additionally, we will consider a facial edge-coloring analogue of the aforementioned coloring.
             

(Joint work with Vesna Andova, Bernard Lidický, Borut Lužar, and Kacy Messerschmidt)