Seminar za kombinatornu i diskretnu matematiku

lokacija: 
PMF Matematički odsjek
vrijeme: 
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
predavanje:
 
 
Riste Skrekovski (Ljubljana): 
         Some results on unique-maximum coloring of plane graphs
 
 
Pozivaju se članovi Seminara te svi zainteresirani da prisustvuju ovom
predavanju
 
Tajnik Seminara
Goran Igaly
 
Sažetak
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