A not 3-choosable planar graph without 3-cycles
type: Item
instance of: scholarly article
title: A not 3-choosable planar graph without 3-cycles
zbMATH Open document ID: 0843.05034
DOI: 10.1016/0012-365X(94)00180-9
published in: Discrete Mathematics
publication date: 1996-08-13T00:00:00Z
review text: A graph \(G\) is \(k\)-choosable if for every list assignment \(v\mapsto L(v)\), where \(L(v)\) is a \(k\)-set \((v\in V(G))\), \(G\) admits a proper coloring such that the color of each vertex \(v\) belongs to \(L(v)\). Thomassen strengthened the 5-color theorem by showing that every planar graph is 5-choosable [\textit{C. Thomassen}, Every planar graph is 5-choosable, J. Comb. Theory, Ser. B 62, No. 1, 180-181 (1994; Zbl 0805.05023)]. Grötzsch proved that every triangle-free planar graph \(G\) admits a 3-coloring, and Thomassen strengthened it to 3-choosability under the stronger condition that the girth of \(G\) is 5 [\textit{C. Thomassen}, 3-list-coloring planar graphs of girth 5, J. Comb. Theory, Ser. B 64, No. 1, 101-107 (1995; Zbl 0822.05029)]. In this paper it is proved that there exists a planar graph of girth 4 which is not 3-choosable.
reviewed by: Bojan Mohar
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 825366
zbMATH Keywords: choosability
zbMATH Keywords: coloring
zbMATH Keywords: planar graph
author: Margit Voigt
MaRDI profile type: Publication
cites work: Colorings and orientations of graphs
cites work: Algorithmic complexity of list colorings
cites work: Q5588433
cites work: Every planar graph is 5-choosable
cites work: 3-list-coloring planar graphs of girth 5
cites work: Q3115277
cites work: List colourings of planar graphs
full work available at URL: 0012-365x(94)00180-9
OpenAlex ID: W2083560794
description: scientific article; zbMATH DE number 825366