Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

DOI10.1016/j.jctb.2021.01.009zbMath1504.05099OpenAlexW3127656805MaRDI QIDQ2099419

Carsten Thomassen

Publication date: 23 November 2022

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2021.01.009

zbMATH Keywords

triangle-free planar graph3-colorings

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12)

Cites Work

• Unnamed Item
• Many 3-colorings of triangle-free planar graphs
• Homomorphisms and edge-colourings of planar graphs
• Exponentially many 5-list-colorings of planar graphs
• Every planar graph is 5-choosable
• A short list color proof of Grötzsch's theorem
• A not 3-choosable planar graph without 3-cycles
• Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs
• 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: Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles