Publication at Faculty of Mathematics and Physics |
2017
Abstract
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 α 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' of A of size at least α|A| such that G-(A-A') is 3-colorable.
This equivalence allows us to study restricted situations, where we can prove the statement to be true.