Springe direkt zu Inhalt

Qianli Wang:

Understanding and implementation of the algorithm for three-coloring in triangle-free planar graphs


Grötzsch's theorem affirms that every planar graph G in which there is no triangle is 3-colorable. Dvorak, Kawarabayashi, and Thomas have designed a linear-time algorithm relying on the Grötzsch's theorem to find a proper 3-coloring of the given graph. Compared to Kowalik who used a data structure called "Short Path Data Structure (SPDS)", it avoids complex data structures, which makes it easier to implement. However, because of the difficulty of their paper and complicated proofs, it's really hard to understand it. So we will explain their main idea and proofs with more illustrations and in detail.

Bachelor of Science (B.Sc.)