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

2010/07/08 by Arash Asadi, Zdenĕk Dvořák, Asadi, Arash +6
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1007.1430

10 pages. Simplified proof. Added a coauthor

openalex publication_date 2010/07/08 · arxiv created 2011/03/30 · arxiv updated 2011/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least 2^[n^(1/12)/20000] distinct 3-colorings. We show that it has at least 2^sqrt(n/362) distinct 3-colorings.

Related

• Triangle-free planar graphs with at most 64^n^0.731 3-colorings
• Three coloring via triangle counting
• 3-Colouring Planar Graphs
• Exponentially Many 4-List-Colorings of Triangle-Free Graphs on Surfaces
• Planar graphs have exponentially many 3-arboricities