University of Primorska Faculty of Mathematics, Natural Sciences and Information Technologies

Mathematical Research Seminar

Mathematical research seminar is organized by the departments of Mathematics of two members of the University - UP FAMNIT and Andrej Marušič Institute (UP IAM), every Monday from October to June.

You are cordially invited to attend the lectures.

Datum in ura / Date and time: 26.4.19
Predavalnica / Location: FAMNIT-MP6
Predavatelj / Lecturer: Riste Škrekovski (UL FMF, UP FAMNIT, IMFM, FIŠ)
Naslov / Title: Some results and problems on unique-maximum colorings of plane graphs
Vsebina / Abstract:

A unique-maximum coloring of a plane graph G is a proper vertex coloring by natural numbers such that each face \alpha of G satisfies the property: the maximal color that appears on \alpha, appears precisely on one vertex of \alpha (or shortly, the maximal color on every face is unique on that face). Fabrici and G\"{o}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. Thus, the facial unique-maximum chromatic number of the sphere is not four but five. In the second part of the talk, we will consider various new directions and open problems.

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