A short list color proof of Grötzsch's theorem

DOI10.1016/S0095-8956(03)00029-7zbMath1025.05022WikidataQ117324772 ScholiaQ117324772MaRDI QIDQ1405112

Carsten Thomassen

Publication date: 25 August 2003

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

zbMATH Keywords

planar graphslist coloringchromating number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (max. 100)

Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle. ⋮ The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs ⋮ Word-Representable Graphs: a Survey ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Do triangle-free planar graphs have exponentially many 3-colorings? ⋮ Homomorphism bounds for oriented planar graphs of given minimum girth ⋮ Many 3-colorings of triangle-free planar graphs ⋮ Additive list coloring of planar graphs with given girth ⋮ Fractional coloring of triangle-free planar graphs ⋮ Kempe equivalence of 4‐critical planar graphs ⋮ Flexibility of triangle‐free planar graphs ⋮ Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$ ⋮ Choosability in signed planar graphs ⋮ Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities ⋮ Flow extensions and group connectivity with applications ⋮ Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five ⋮ On spanning trees without vertices of degree 2 in plane triangulations ⋮ From the plane to higher surfaces ⋮ Fast 3-coloring triangle-free planar graphs ⋮ Ore's conjecture on color-critical graphs is almost true ⋮ Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ On 3-choosability of triangle-free plane graphs ⋮ Concepts of signed graph coloring ⋮ An introduction to the discharging method via graph coloring ⋮ Coloring even-faced graphs in the torus and the Klein bottle ⋮ Geometric spanners with small chromatic number ⋮ 2-list-coloring planar graphs without monochromatic triangles ⋮ On group choosability of graphs. II ⋮ What is on his mind? ⋮ Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk ⋮ Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs ⋮ Group connectivity and group coloring: small groups versus large groups ⋮ On 3-choosable planar graphs of girth at least 4 ⋮ Decomposing a planar graph of girth 5 into an independent set and a forest ⋮ Multiple list colouring triangle free planar graphs ⋮ Nowhere-zero 3-flows in toroidal graphs ⋮ Adapted list coloring of planar graphs ⋮ Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor ⋮ Sub-Exponentially Many 3-Colorings of Triangle-Free Planar Graphs ⋮ List colorings with distinct list sizes, the case of complete bipartite graphs ⋮ Some of My Favorite Coloring Problems for Graphs and Digraphs ⋮ Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles ⋮ Ergodicity of the Wang–Swendsen–Kotecký algorithm on several classes of lattices on the torus ⋮ On sufficient conditions for planar graphs to be 5-flexible

Cites Work

• Unnamed Item
• Every planar graph is 5-choosable
• 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
• 3-list-coloring planar graphs of girth 5

This page was built for publication: A short list color proof of Grötzsch's theorem