Many 3-colorings of triangle-free planar graphs

DOI10.1016/j.jctb.2006.06.005zbMath1118.05038OpenAlexW1988876227WikidataQ56926656 ScholiaQ56926656MaRDI QIDQ875936

Carsten Thomassen

Publication date: 16 April 2007

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.2006.06.005

zbMATH Keywords

list-colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (max. 100)

Hyperbolic families and coloring graphs on surfaces ⋮ Do triangle-free planar graphs have exponentially many 3-colorings? ⋮ A General Framework for Hypergraph Coloring ⋮ Exponentially many 5-list-colorings of planar graphs ⋮ Triangle-free planar graphs with at most \(64^{n^{0.731}}\) 3-colorings ⋮ Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles ⋮ An algebraic approach for counting DP-3-colorings of sparse graphs ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ Graphs with full rank 3-color matrix and few 3-colorings ⋮ What is on his mind? ⋮ Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows ⋮ Exponentially many \(\mathbb{Z}_5\)-colorings in simple planar graphs ⋮ Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies ⋮ The chromatic polynomial and list colorings ⋮ 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The number of \(k\)-colorings of a graph on a fixed surface
• 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
• Color-critical graphs on a fixed surface
• 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
• Coloring graphs with fixed genus and girth
• The color space of a graph
• Algorithms – ESA 2004

This page was built for publication: Many 3-colorings of triangle-free planar graphs