Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

Abstract The number of proper vertex-3-colorings of every triangle-free planar graph with n vertices and with no separating cycle of length 4 or 5 is at least 2 n / 17700000 . On the other hand, for infinitely many n, there exists a triangle-free planar graph with separating cycles of length 4 and 5 whose number of proper vertex-3-colorings is 2 15 n / log 2 ⁡ ( n ) .