A not 3-choosable planar graph without 3-cycles Artikel uri icon

Open Access

  • false

Peer Reviewed

  • true

Abstract

  • An L- list coloring of a graph G is a proper vertex coloring in which every vertex v receives a color from a prescribed list L( v). G is called k- choosable if all lists L( v) have the cardinality k and G is L-list colorable for all possible assignments of such lists. Recently, Thomassen has proved that every planar graph with girth greater than 4 is 3-choosable. Furthermore, it is known that the chromatic number of a planar graph without 3-cycles is at most 3. Consequently, the question resulted whether every planar graph without 3-cycles is 3-choosable. In the following we will give a planar graph without 3-cycles which is not 3-choosable.