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

zbMath1369.05074arXiv1702.00588MaRDI QIDQ2401433

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

zbMATH Keywords

planar graphstriangle-free graphsGrötzsch's theoremmany 3-colorings

Mathematics Subject Classification ID

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

Related Items (max. 100)

A General Framework for Hypergraph Coloring

Cites Work

• Many 3-colorings of triangle-free planar graphs
• Homomorphisms and edge-colourings of planar graphs
• 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
• A not 3-choosable planar graph without 3-cycles
• Three-coloring triangle-free planar graphs in linear time
• The color space of a graph
• Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles

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