3-list-coloring planar graphs of girth 5
type: Item
instance of: scholarly article
title: 3-list-coloring planar graphs of girth 5
zbMATH Open document ID: 0822.05029
author: Carsten Thomassen
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-07-04T00:00:00Z
review text: If each vertex of a graph \(G\) is assigned a list \(L(v)\) of natural numbers, then a list coloring of \(G\) is a map from \(V(G)\) to \(\mathbb{N}\) such that each \(v\) is mapped into \(L(v)\) and adjacent vertices always receive distinct numbers (colors). Then \(G\) is \(k\)-choosable if \(G\) has a list coloring for each list assignment with \(k\) colors in each list, and \(k\)- colorable if \(G\) has a list coloring with all lists being \(\{1, 2, 3,\dots, k\}\). The author proves, using only vertex deletion and induction, that every planar graph of girth at least 5 is 3-choosable, even with the precoloring of any 5-cycle. This extension allows an immediate proof of Grötzsch's theorem that every planar graph of girth at least 4 is 3-colorable.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 767701
zbMATH Keywords: list coloring
zbMATH Keywords: planar graph
reviewed by: Arthur T. White
MaRDI profile type: Publication
full work available at URL: jctb.1995.1027
OpenAlex ID: W2017043109
DOI: 10.1006/JCTB.1995.1027
description: scientific article; zbMATH DE number 767701