Thomassen's coloring-growth conjecture for triangle-free planar graphs

About 16 years old · traced to

Let GG be an nn-vertex triangle-free planar graph. A proper 3-coloring of GG is a vertex coloring with three colors in which adjacent vertices receive different colors. Thomassen's coloring-growth conjecture. There exists a constant c>1c>1 such that every nn-vertex triangle-free planar graph has at least

cnlog⁡9/23c^{n^{\log_{9/2}3}}

distinct proper 3-colorings. Thomassen's original exponential lower-bound conjecture was disproved by examples with only 215n/log⁡2n2^{15n/\log_2 n} 3-colorings; the stated power-law bound is conjectured to be tight because the paper's construction attains the exponent log⁡9/23\log_{9/2}3 for infinitely many values of nn.

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

Never refreshed

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.