List colorings and reducibility
type: Item
instance of: scholarly article
title: List colorings and reducibility
zbMATH Open document ID: 0882.05055
DOI: 10.1016/S0166-218X(97)00046-2
author: Zsolt Tuza
author: Margit Voigt
published in: Discrete Applied Mathematics
publication date: 1998-01-28T00:00:00Z
full work available at URL: dam
review text: Let \(G\) be a simple graph, \(L(v)\) a list of allowed colors assigned to each vertex \(v\) of \(G\), and \(U\) an arbitrary subset of the vertex set. The graph \(G\) is called \(k\)-choosable if, for any list assignment with \(|L(v)|=k\) for all \(v\in V\), it is possible to color all vertices with colors from their lists in a proper way (i.e., no monochromatic edge occurs). We say that \(G\) is \(U\)-reducible if, for every list assignment of \(G\) where all lists have the same number of elements, we can color the vertices of \(U\) with colors from their lists such that for every vertex \(v\notin U\) at most one color of \(L(v)\) appears in the coloring of the neighbors of \(v\) which belong to \(U\). The concept of reducibility is closely related to list colorings and choosability. The main result of this paper states that a bipartite graph \(G\) is \(U\)-reducible for every maximal independent set \(U\subseteq V\) if and only if \(G\) is 2-choosable. It is also proved that if \(G\) is 2-choosable, then it is \(U\)-reducible for every \(U\subseteq V\), and that the Petersen graph, \(K_{3,4}\) and \(K_{3,5}\) are \((3m,m)\)-choosable for all \(m\geq 1\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1088867
zbMATH Keywords: list coloring
zbMATH Keywords: \(k\)-choosable graph
zbMATH Keywords: \(U\)-reducible graph
zbMATH Keywords: bipartite graph
zbMATH Keywords: Petersen graph
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Q4882474
cites work: Q4888118
cites work: Q4135588
cites work: Graph colorings with local constraints -- a survey
OpenAlex ID: W2028983129
Recommended article: On the number of list‐colorings
Recommended article: A note on list-colorings
Recommended article: Q3615791
Recommended article: List-colourings of graphs
Recommended article: The chromatic polynomial and list colorings
Recommended article: Algorithmic complexity of list colorings
Recommended article: A Note on Partial List Colorings
Recommended article: Partial list colorings
Recommended article: A Hajós-like theorem for list coloring
Recommended article: List Set Colouring: Bounds and Algorithms
description: scientific article; zbMATH DE number 1088867