行知论坛210:Some results and problems on unique-maximum colorings of plane graphs

时间:2019-07-08浏览:104设置

行知论坛 第210(海外学术报告)


报告时间:2019711日上午10:00

报告地点:计算机学院4042

报告题目:Some results and problems on unique-maximum colorings of plane graphs

报 告 人:Riste Skrekovski (研究员,University of Ljubljana)

邀 请 人:王贝贝

报告简介: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 propety:  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.

报告人简介:Riste Škrekovski obtained his PhD degree in graph colorings at the University of Ljubljana in 2000 and continued his postdoctoral education at Charles University, Prague, Czech Republic and Simon Fraser University, Burnaby, Canada. Nowadays, he is one of the leading researchers at Faculty of Information Studies of Novo mesto, Slovenia and teach discrete mathematics courses at University of Ljubljana.  His main research interests are various topics in classical graph theory, but he is also interested in applied and interdisciplinary areas as chemical mathematics, complex networks, the arts and mathematics,...




返回原图
/