Partial list colorings
type: Item
instance of: scholarly article
title: Partial list colorings
zbMATH Open document ID: 0957.05037
DOI: 10.1016/S0012-365X(99)00315-5
author: Sara Grossman
author: Ruth Haas
author: Michael O. Albertson
published in: Discrete Mathematics
publication date: 2000-03-23T00:00:00Z
review text: Let \(R= \{1,2,\dots, r\}\) be a set of colors, and let \(\ell: V(G)\to 2^R\) be a function. A proper coloring \(c: V(G)\to R\) is said to be a list coloring if \(c(x)\in\ell(x)\) for all \(x\). If there is an integer \(s\) such that all functions \(\ell\) with \(|\ell(x)|= s\) have a list coloring, then \(G\) is said to be \(s\)-choosable. The authors conjecture that when \(G\) is \(s\)-choosable, for every \(\ell\) with \(|\ell(x)|= t\) there are at least \(({t\over s})n\) vertices that can be colored by \(\ell\). Lower bounds involving old and new parameters for graphs are proved.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1423744
zbMATH Keywords: independence number
zbMATH Keywords: chromatic number
zbMATH Keywords: list coloring
reviewed by: Raffaele Scapellato
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00315-5
OpenAlex ID: W2136876085
description: scientific article; zbMATH DE number 1423744