Seminár z teórie grafov - Riste Skrekovski (21.3.2019)

vo štvrtok 21.3.2019 o 9:50 hod. v posluchárni C

---

Prednášajúci: Riste Skrekovski (University of Ljubljana)

Názov: Some results on the unique-maximum coloring of plane graphs

Termín: 21.3.2019, 9:50 hod., poslucháreň C

Abstrakt:
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\"oring 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.

Joint work with Vesna Andova, Bernard Lidicky, Borut Luzar, and Kacy Messerschmidt.

---