Do Triangle-Free Planar Graphs have Exponentially Many $3$-Colorings?

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 make...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2017-09, Vol.24 (3)
Main Authors: Dvořák, Zdeněk, Sereni, Jean-Sébastien
Format: Article
Language:English
Subjects:
Combinatorics
Mathematics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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'$ 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.
ISSN:1077-8926
1077-8926
DOI:10.37236/6736