Complexity of list coloring problems with a fixed total number of colors
type: Item
instance of: scholarly article
title: Complexity of list coloring problems with a fixed total number of colors
zbMATH Open document ID: 0990.05042
DOI: 10.1016/S0166-218X(01)00179-2
author: Sylvain Gravier
author: Daniel Kobler
author: Wieslaw Kubiak
published in: Discrete Applied Mathematics
publication date: 2002-05-15T00:00:00Z
review text: In the list coloring problem, a graph \(G=(V,E)\) is given and with each vertex \(v\), a list of colors \(L(v)\). The problem is to select for each vertex a color from its list such that adjacent vertices get different colors. This paper looks at versions of the problem where additionally there is a function \(p\), such that each color \(j\) is given to exactly (or respectively at most) \(p(j)\) vertices. The paper establishes NP-completeness for the problem when there are three colors for bipartite planar graphs, and shows it is polynomially time solvable when there are two colors. The paper also shows that for a fixed number of colors, the problems (and the standard list coloring problem) are polynomially solvable for treeds and for graphs of bounded treewidth. Treeds can be defined as follows. A forest is a treed. If we have a treed and replace one vertex \(v\) by a treed such that each vertex in the latter treed is exactly adjacent to all neighbors of \(v\), then we again have a treed.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1742048
zbMATH Keywords: complexity
zbMATH Keywords: list coloring
zbMATH Keywords: treed graphs
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
cites work: Precoloring extension. I: Interval graphs
cites work: Q4291429
cites work: Q4699283
cites work: A Fast Algorithm for the Decomposition of Graphs and Posets
cites work: Complement reducible graphs
cites work: Q4954442
cites work: On the vertex packing problem
cites work: On the complexity of a restricted list-coloring problem
cites work: Q3922703
cites work: Arrays of distinct representatives --- a very simple NP-complete problem
cites work: Q4198056
cites work: Q3328583
cites work: On the X-join decomposition for undirected graphs
cites work: Generalized coloring for tree-like graphs
cites work: Q4838453
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Q3128916
cites work: On a property of the class of n-colorable graphs
cites work: Restricted coloring models for timetabling
description: scientific article; zbMATH DE number 1742048