Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs

DOI10.1016/j.endm.2009.07.014zbMath1272.05042arXiv1007.1430OpenAlexW2571248631MaRDI QIDQ2851443

Robin Thomas, Arash Sh. Asadi, Luke Postle

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coloring graphstriangle-free planar graphs

Mathematics Subject Classification ID

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

Related Items (max. 100)

Outerspatial 2-complexes: extending the class of outerplanar graphs to three dimensions ⋮ Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs ⋮ Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

Cites Work

• Many 3-colorings of triangle-free planar graphs
• Exponentially many 5-list-colorings of planar graphs
• Every planar graph is 5-choosable
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• A short list color proof of Grötzsch's theorem
• 3-list-coloring planar graphs of girth 5
• Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs
• Algorithms – ESA 2004
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs