Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Claims
1993_09_01_voigt: Voigt (Discrete Math. 1993) constructs a planar graph on 238 vertices that is not 4-choosable, so the bound 5 is best possible; accepted on the refereed publication and the site's credit.
1994_09_01_thomassen: Thomassen (J. Combin. Theory Ser. B 1994) proves that every planar graph has list chromatic number at most 5, answering the first question yes; accepted on the refereed publication and the site's credit.
1996_01_01_mirzakhani: Mirzakhani (Bull. Inst. Combin. Appl. 1996) gives a 3-colorable planar graph on 63 vertices that is not 4-choosable, a smaller witness than Voigt's and Gutner's that 5 is best possible; accepted on the refereed publication.
1996_11_01_gutner: Theorem 1.7 of Gutner (Discrete Math. 1996) gives a planar graph on 75 vertices that is not 4-choosable, a smaller witness that 5 is best possible; accepted on the refereed publication and the site's credit.