Publication at Faculty of Mathematics and Physics |
2022
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 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.