Vertex colorings of graphs embedded on surfaces with face
constraints have recently attracted a lot of attention of
researchers. In this talk, we focus mainly on vertex colorings of
plane graphs with no rainbow faces, i.e., a face in which all
vertices receive distinct colors. As an application of Tutte's
theorem on the existence of perfect matchings, we prove a
conjecture of Ramamurthi and West that vertices of each n-vertex
triangle-free plane graph can be colored with at least n/2+1
colors avoiding a rainbow face. The derived bound is the best
possible. In addition, we derive optimal bounds on the number of
colors also for n-vertex plane graphs with girth g
³ 5.
∼Daniel Kral 教授演講摘要∼