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
    0 references
    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

    Identifiers