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

Abstrakt

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 215n/ log2 n 3-colorings.

We improve his construction, giving examples of such graphs with at most 64(nlog9/2 3) < 64n(0.731 3)-colorings. We conjecture this exponent is optimal. (c) 2022 Elsevier Inc.

All rights reserved.

Klíčová slova

• Triangle-free
• Planar
• Number of colorings