Do triangle-free planar graphs have exponentially many 3-colorings? (Q2401433)

Summary: Thomassen conjectured that triangle-free planar graphs have an exponential number of 3-colorings. We show this conjecture to be equivalent to the following statement: there exists a positive real \(\alpha\) such that whenever \(G\) is a planar graph and \(A\) is a subset of its edges whose deletion makes \(G\) triangle-free, there exists a subset \(A^\prime\) of \(A\) of size at least \(\alpha|A|\) such that \(G-(A\setminus A^\prime)\) is 3-colorable. This equivalence allows us to study restricted situations, where we can prove the statement to be true.