A short list color proof of Grötzsch's theorem
From MaRDI portal
Publication:1405112
In [\textit{C. Thomassen}, J. Comb. Theory, Ser. B 64, 101-107 (1995; Zbl 0822.05029)] it was proved that every planar graph of girth 5 is 3-list-colorable. In the present note, the author gives a short proof of this result. This result and its proof are used in [\textit{C. Thomassen}, J. Comb. Theory, Ser. B 87, 38-71 (2003; Zbl 1020.05030)] to conclude that the chromatic number of graphs of girth 5 on every fixed surface can be found in polynomial time.
Recommendations
- A Grötzsch-Type Theorem for List Colourings with Impropriety One
- Short proofs of the Kneser-Lovász coloring principle
- Short proofs of the Kneser-Lovász coloring principle
- A Coloring Proof of a Generalisation of Fermat's Little Theorem
- Short proofs of coloring theorems on planar graphs
- A new proof of Grünbaum's 3 color theorem
- A Hajós-like theorem for list coloring
- A Colored Version of Tverberg's Theorem
- Gallai's theorem for list coloring of digraphs
- Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph
Cites work
Cited in
(59)- On 3-choosable planar graphs of girth at least 4
- Decomposing a planar graph of girth 5 into an independent set and a forest
- Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
- 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
- Short proofs of the Kneser-Lovász coloring principle
- 3-list-coloring planar graphs of girth 5
- Fast 3-coloring triangle-free planar graphs
- On group choosability of graphs. II
- Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
- Nowhere-zero 3-flows in toroidal graphs
- Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles
- On sufficient conditions for planar graphs to be 5-flexible
- Additive list coloring of planar graphs with given girth
- 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
- 3-list-coloring graphs of girth at least five on surfaces
- Concepts of signed graph coloring
- Group connectivity and group coloring: small groups versus large groups
- Multiple list colouring triangle free planar graphs
- Do triangle-free planar graphs have exponentially many 3-colorings?
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- Sub-exponentially many 3-colorings of triangle-free planar graphs
- List colorings with distinct list sizes, the case of complete bipartite graphs
- Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
- Short proofs for two theorems of Chien, Hell and Zhu
- Adapted list coloring of planar graphs
- Homomorphism bounds for oriented planar graphs of given minimum girth
- From the plane to higher surfaces
- Word-Representable Graphs: a Survey
- Hyperbolic families and coloring graphs on surfaces
- Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count
- Ore's conjecture on color-critical graphs is almost true
- A Grötzsch-Type Theorem for List Colourings with Impropriety One
- Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
- The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
- An introduction to the discharging method via graph coloring
- Some of my favorite coloring problems for graphs and digraphs
- Ergodicity of the Wang–Swendsen–Kotecký algorithm on several classes of lattices on the torus
- Kempe equivalence of 4‐critical planar graphs
- Flexibility of triangle‐free planar graphs
- Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
- 3-flows and combs
- On 3-choosability of triangle-free plane graphs
- Nowhere-zero 3-flows in signed planar graphs
- Online 3-choosability of a planar graph without certain cycles
- The four color theorem and its aftermath
- Hyperbolicity theorems for correspondence colouring
- Sub-exponentially many 3-colorings of triangle-free planar graphs
- What is on his mind?
- Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
- Defective and clustered colouring of graphs with given girth
- Many 3-colorings of triangle-free planar graphs
- Fractional coloring of triangle-free planar graphs
- Choosability in signed planar graphs
- 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
This page was built for publication: A short list color proof of Grötzsch's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1405112)
