Seminar za kombinatornu i diskretnu matematiku

PMF Matematički odsjek
17.04.2018 - 16:00 - 17:30
U utorak, 17. travnja 2018. u predavaonici 108 u 16 sati
u okviru Seminara za kombinatornu i diskretnu matematiku održat će se
Riste Skrekovski (Ljubljana): 
         Some results on unique-maximum coloring of plane graphs
Pozivaju se članovi Seminara te svi zainteresirani da prisustvuju ovom
Tajnik Seminara
Goran Igaly
A unique-maximum coloring of a plane graph is a proper vertex
coloring by natural numbers where on each face the maximal color
appears exactly once on the vertices of α. 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)
Share this