A short list color proof of Grötzsch's theorem (Q1405112): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q117324772, #quickstatements; #temporary_batch_1704605156744 |
ReferenceBot (talk | contribs) Changed an Item |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5752592 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Every planar graph is 5-choosable / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: 3-list-coloring planar graphs of girth 5 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The chromatic number of a graph of girth 5 on a fixed surface / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 09:20, 6 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A short list color proof of Grötzsch's theorem |
scientific article |
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
