A note on the not 3-choosability of some families of planar graphs

摘要

A graph G is L-list colorable if for a given list assignment L = {L(υ): υ ∈ V}, there exists a proper coloring c of G such that C(υ) ∈ L(υ) for all υ ∈ V. If G is L-list colorable for any list assignment with |L(υ)| ≥ k for all υ ∈ V, then G is said k-choosable. In [M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325-328] and [M. Voigt, A non-3-choosable planar graph without cycles of length 4 and 5, 2003, Manuscript], Voigt gave a planar graph without 3-cycles and a planar graph without 4-cycles and 5-cycles which are not 3-choosable. In this note, we give smaller and easier graphs than those proposed by Voigt and suggest an extension of Erdoes' relaxation of Steinberg's conjecture to 3-choosability.