On the complexity of a restricted list-coloring problem

DOI10.1016/S0012-365X(98)00169-1zbMATH Open0928.05057MaRDI QIDQ1296975FDOQ1296975

Moshe Dror, Wieslaw Kubiak, Gerd Finke, Sylvain Gravier

Publication date: 3 August 1999

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

Recommendations

• Publication:4934399
• scientific article; zbMATH DE number 1955762
• Algorithmic complexity of list colorings
• Some results concerning the complexity of restricted colorings of graphs
• Complexity of list coloring problems with a fixed total number of colors

zbMATH Keywords

polynomial algorithmrestricted list-coloring

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted coloring models for timetabling
• Scheduling tasks on two processors with deadlines and additional resources

Cited In (15)

• Space complexity of list H-colouring: a dichotomy
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• Exploring the complexity boundary between coloring and list-coloring
• Approximating List-Coloring on a Fixed Surface
• Complexity of list coloring problems with a fixed total number of colors
• Bounded max-colorings of graphs
• Proportional choosability: a new list analogue of equitable coloring
• Consensus models: computational complexity aspects in modern approaches to the list coloring problem
• Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
• Algorithmic complexity of list colorings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296975)