Do triangle-free planar graphs have exponentially many 3-colorings?

zbMATH Open1369.05074arXiv1702.00588MaRDI QIDQ2401433FDOQ2401433

Authors: Zdeněk Dvořák, Jean-Sébastien Sereni 

Publication date: 8 September 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 $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-(Asetminus{A}^{\prime })$ is $3$-colorable. This equivalence allows us to study restricted situations, where we can prove the statement to be true.

Full work available at URL: https://arxiv.org/abs/1702.00588

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• Many 3-colorings of triangle-free planar graphs
• Triangle-free planar graphs with at most \(64^{n^{0.731}}\) 3-colorings
• Three-coloring triangle-free planar graphs in linear time
• Three-coloring triangle-free planar graphs in linear time
• Three-colourability of planar graphs with no 5- or triangular \(\{3,6\}\)-cycles
• Algorithms – ESA 2004
• Fast 3-coloring triangle-free planar graphs
• Planar graphs have exponentially many 3-arboricities

zbMATH Keywords

planar graphstriangle-free graphs[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDtzsch%27s+theorem&go=Go Gr��tzsch's theorem]many 3-colorings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• The chromatic number of a graph of girth 5 on a fixed surface
• A short list color proof of Grötzsch's theorem
• 3-list-coloring planar graphs of girth 5
• Three-coloring triangle-free planar graphs in linear time
• Many 3-colorings of triangle-free planar graphs
• Homomorphisms and edge-colourings of planar graphs
• A not 3-choosable planar graph without 3-cycles
• The color space of a graph
• Fine structure of 4-critical triangle-free graphs. II: Planar triangle-free graphs with two precolored 4-cycles

Cited In (6)

• Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles
• Flexibility of planar graphs without 4-cycles
• Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• Planar graphs have exponentially many 3-arboricities
• A general framework for hypergraph coloring

This page was built for publication: Do triangle-free planar graphs have exponentially many 3-colorings?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401433)