Sub-exponentially many 3-colorings of triangle-free planar graphs

Abstrakt

Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least 2(n1/12/20) (000) distinct 3-colorings. We show that it has at least 2(root n/212) distinct 3-colorings.

Klíčová slova

• Graph
• Coloring
• Triangle-free planar graph