Fast 3-coloring Triangle-Free Planar Graphs

摘要

Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n 2) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is .