Thomassen's coloring-growth conjecture for triangle-free planar graphs
Let be an -vertex triangle-free planar graph. A proper 3-coloring of is a vertex coloring with three colors in which adjacent vertices receive different colors. Thomassen's coloring-growth conjecture. There exists a constant such that every -vertex triangle-free planar graph has at least
distinct proper 3-colorings. Thomassen's original exponential lower-bound conjecture was disproved by examples with only 3-colorings; the stated power-law bound is conjectured to be tight because the paper's construction attains the exponent for infinitely many values of .
References
Primary source
Zdeněk Dvořák and Luke Postle, “Triangle-free planar graphs with at most 64^n^0.731 3-colorings”, arXiv:2108.12669 (2021).
Additional references
3 papers in this index state this conjecture (2010–2021). The statement above is taken from the most recent of them; the others are arXiv:1702.00588, arXiv:1007.1430.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.