Do triangle-free planar graphs have exponentially many 3-colorings? (Q2401433)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Do triangle-free planar graphs have exponentially many 3-colorings? |
scientific article |
Statements
Do triangle-free planar graphs have exponentially many 3-colorings? (English)
0 references
8 September 2017
0 references
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.
0 references
many 3-colorings
0 references
planar graphs
0 references
triangle-free graphs
0 references
Grötzsch's theorem
0 references
0 references