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

MaRDI QIDQ2401433zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1702.00588, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p47

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

zbMATH Keywords

planar graphstriangle-free graphsmany 3-coloringsGrötzsch's theorem

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(6)

• Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles
• Planar graphs have exponentially many 3-arboricities
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows
• Flexibility of planar graphs without 4-cycles
• 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)