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'$ of $A$ of size at least $\alpha|A|$ such that $G-(A\setminus A')$ is $3$-colorable. This equivalence allows us to study restricted situations, where we can prove the statement to be true.
@article{10_37236_6736,
author = {Zden\v{e}k Dvo\v{r}\'ak and Jean-S\'ebastien Sereni},
title = {Do triangle-free planar graphs have exponentially many 3-colorings?},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {3},
doi = {10.37236/6736},
zbl = {1369.05074},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6736/}
}
TY - JOUR
AU - Zdeněk Dvořák
AU - Jean-Sébastien Sereni
TI - Do triangle-free planar graphs have exponentially many 3-colorings?
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/6736/
DO - 10.37236/6736
ID - 10_37236_6736
ER -
%0 Journal Article
%A Zdeněk Dvořák
%A Jean-Sébastien Sereni
%T Do triangle-free planar graphs have exponentially many 3-colorings?
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/6736/
%R 10.37236/6736
%F 10_37236_6736
Zdeněk Dvořák; Jean-Sébastien Sereni. Do triangle-free planar graphs have exponentially many 3-colorings?. The electronic journal of combinatorics, Tome 24 (2017) no. 3. doi: 10.37236/6736
