List improper colorings of planar graphs with prescribed girth
type: Item
instance of: scholarly article
title: List improper colorings of planar graphs with prescribed girth
zbMATH Open document ID: 0940.05027
DOI: 10.1016/S0012-365X(99)00145-4
author: Riste Škrekovski
published in: Discrete Mathematics
publication date: 2000-06-22T00:00:00Z
review text: A graph \(G\) is said to be \((m,d)^{*}\)-choosable, if for every list assignment \(L\), where \(|L(v)|\geq m\) for every \(v\in V(G)\), there exists an \(L\)-coloring of \(G\) such that every vertex of \(G\) has at most \(d\) neighbors colored with the same color as itself. Denote by \(g_{d}\) the smallest number such that every planar graph of girth at least \(g_{d}\) is \((2,d)^{*}\)-choosable. In this paper it is shown that \(6\leq g_{1}\leq 9\); \(2\leq g_{2}\leq 7\); \(5\leq g_{3}\leq 6\) and \(g_{d}=5\) for every \(d\geq 4\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1423743
zbMATH Keywords: planar graph
zbMATH Keywords: girth
zbMATH Keywords: choosable graph
zbMATH Keywords: list coloring
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00145-4
OpenAlex ID: W2083796113
description: scientific article; zbMATH DE number 1423743