Triangle-free planar graphs with at most 64ⁿ^0.731 3-colorings

DOI10.1016/J.JCTB.2022.05.003MaRDI QIDQ2673487zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Luke Postle

Publication date 10 June 2022

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

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

zbMATH Keywords

number of coloringstriangle-free

Mathematics Subject Classification ID

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

Abstract: Thomassen conjectured that triangle-free planar graphs have exponentially many 3-colorings. Recently, he disproved his conjecture by providing examples of such graphs with $n$ vertices and at most $2^{15n/lo{g}_{2}n}$ 3-colorings. We improve his construction, giving examples of such graphs with at most $64^{n^{lo{g}_{9/2}3}}<64^{n^{0.731}}$ 3-colorings. We conjecture this exponent is optimal.

Recommendations

• Many 3-colorings of triangle-free planar graphs
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• 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
• Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles
• Algorithms – ESA 2004
• Fast 3-coloring triangle-free planar graphs
• Total colorings of planar graphs with sparse triangles
• Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles

Cites work

• Chromatic Polynomials
• Many 3-colorings of triangle-free planar graphs
• Planar 4-critical graphs with four triangles

Cited in

(8)

• Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles
• Do triangle-free planar graphs have exponentially many 3-colorings?
• Sub-exponentially many 3-colorings of triangle-free planar graphs
• Three-coloring triangle-free planar graphs in linear time
• Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows
• Decomposition of triangle-free planar graphs
• Many 3-colorings of triangle-free planar graphs
• Graphs with full rank 3-color matrix and few 3-colorings

This page was built for publication: Triangle-free planar graphs with at most \(64^{n^{0.731}}\) 3-colorings

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