讲座 | Steinberg's Conjecture - Coloring of Plane Graphs
主讲人: 林子波教授
时间: 2013年5月29日（星期三），下午2:00-3:00
地点: E202
摘要:
The Four Color Theorem implies that any planar graph can be colored with 4 colors without adjacent vertices receiving the same color (4-colorable). The number 4 is best possible, since K4 is planar and cannot be 3-colored. Whether a graph requires 2 colors is easy to determine: any graph containing cycles of odd length is not 2-colorable. Thus the remaining problem for coloring planar graphs is determining which planar graphs can be 3-colored. Unfortunately, the problem of determinging whether a planar graph is 3-colorable is NP-complete. That leads to the Steinberg’s Conjecture (1970 or so), which states that any planar graph without 4- or 5-cycles is 3-colorable. Despite some claims on having proved the Conjecture, the general consensus is that it is still outstanding. However, the attempt to prove this Conjecture led to lots of other results as well as lots of new outstanding problems. This talk attempts to give a brief outline on the new results, and the possible direction of work which might prove to be fruitful.