Subexponential lower bound for triangle-free planar 3-colorings
Conjecture 1 · arXiv:2108.12669
Status open high confidence
Conjecture 1 from arXiv:2108.12669 asserts that the exponent $\log_{9/2} 3 \approx 0.731$ in the upper bound of the same paper is optimal, i.e., every $n$-vertex triangle-free planar graph has at least $c^{n^{\log_{9/2} 3}}$ distinct proper 3-colorings for some constant $c > 1$. The best known lower bounds on the number of 3-colorings of triangle-free planar graphs (e.g., sub-polynomial exponents from Thomassen's work and related reformulations such as arXiv:1702.00588) fall far short of the conjectured exponent. No paper proving or disproving the full conjecture was found in a wide web search.
Reviewer notes. No follow-up paper resolving the conjecture was found. The conjecture is closely related to Thomassen's conjecture that triangle-free planar graphs have exponentially many 3-colorings, which itself remains open. The paper arXiv:1702.00588 (Dvořák–Postle, 2017) reformulates Thomassen's conjecture as an edge-deletion equivalence but proves no lower bound on colorings. The best known unconditional lower bounds achieve a much smaller exponent than the conjectured $\log_{9/2} 3 \approx 0.731$.
Context
Theorem 1 of the paper provides, for infinitely many $n$, an $n$-vertex triangle-free planar graph with at most $64^{n^{\log_{9/2} 3}} < 64^{n^{0.731}}$ 3-colorings, improving Thomassen's construction. The authors conjecture that the exponent $\log_{9/2} 3 \approx 0.731$ in the upper bound is optimal, making Conjecture 1 the matching lower-bound statement.
Notes. PDF source — the exponent 'nlog9/23' in the raw extraction is read as $n^{\log_{9/2} 3}$, consistent with the stated numerical approximation $n^{0.731}$ and the analytic derivation in the proof.
Source paper
Triangle-free planar graphs with at most $64^{n^{0.731}}$ 3-colorings
Zdeněk Dvořák, Luke Postle · 2021-08-28
https://arxiv.org/abs/2108.12669
PDF source