A short list color proof of Grötzsch's theorem (Q1405112)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1970685
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A short list color proof of Grötzsch's theorem |
scientific article; zbMATH DE number 1970685 |
Statements
A short list color proof of Grötzsch's theorem (English)
0 references
25 August 2003
0 references
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.
0 references
chromating number
0 references
list coloring
0 references
planar graphs
0 references
0.88460684
0 references
0.8834938
0 references
0.8834938
0 references
0.88340855
0 references
0.87816906
0 references
0.87665844
0 references
0 references
0.8724042
0 references
0.8619796
0 references
