On the complexity of a restricted list-coloring problem

DOI10.1016/S0012-365X(98)00169-1zbMath0928.05057MaRDI QIDQ1296975

Moshe Dror, Gerd Finke, Sylvain Gravier, Wiesław X. Kubiak

Publication date: 3 August 1999

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmrestricted list-coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Complexity of list coloring problems with a fixed total number of colors ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Consensus models: computational complexity aspects in modern approaches to the list coloring problem ⋮ Bounded max-colorings of graphs ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Proportional choosability: a new list analogue of equitable coloring

Cites Work

• Scheduling tasks on two processors with deadlines and additional resources
• Restricted coloring models for timetabling
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of a restricted list-coloring problem