Triangle-free planar graphs with at most 64^n^0.731 3-colorings

2021/08/28 by Zdeněk Dvořák, Dvořák, Zdeněk, Luke Postle +1
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.2108.12669

4 pages, 1 figure

arxiv created 2021/08/28 · arxiv updated 2021/08/31

Abstract

Thomassen conjectured that triangle-free planar graphs have exponentially many 3-colorings. Recently, he disproved his conjecture by providing examples of such graphs with n vertices and at most 2^{15n/log₂ n} 3-colorings. We improve his construction, giving examples of such graphs with at most 64^n^log_9/2 3<64^n^0.731 3-colorings. We conjecture this exponent is optimal.

Related

• Sub-exponentially many 3-colorings of triangle-free planar graphs
• 3-Colouring Planar Graphs
• Three coloring via triangle counting
• 3 List Coloring Graphs of Girth at least Five on Surfaces
• On Wegner's 8-Coloring Theorem for Planar Graphs of Maximum Degree Three