A not 3-choosable planar graph without 3-cycles

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1995-11, Vol.146 (1), p.325-328
Main Author: Voigt, Margit
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/0012-365X(94)00180-9