On the complexity of a restricted list-coloring problem

DOI10.1016/S0012-365X(98)00169-1MaRDI QIDQ1296975zbMATHFDO

Authors Moshe Dror, Gerd Finke, Sylvain Gravier, Wieslaw 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

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)

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

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• Multicriterial graph problems with MAXMIN criterion
• Restricted coloring models for timetabling
• Scheduling tasks on two processors with deadlines and additional resources

Cited in

(17)

• scientific article; zbMATH DE number 446487 (Why is no real title available?)
• Space complexity of list H-colouring: a dichotomy
• Exploring the complexity boundary between coloring and list-coloring
• scientific article; zbMATH DE number 1390129 (Why is no real title available?)
• scientific article; zbMATH DE number 1744077 (Why is no real title available?)
• scientific article; zbMATH DE number 1560505 (Why is no real title available?)
• Approximating List-Coloring on a Fixed Surface
• Proportional choosability: a new list analogue of equitable coloring
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• On list coloring and list homomorphism of permutation and interval graphs
• Algorithmic complexity of list colorings
• scientific article; zbMATH DE number 1955762 (Why is no real title available?)
• Complexity of list coloring problems with a fixed total number of colors
• Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
• Bounded max-colorings of graphs
• Colored-independence on paths
• Consensus models: computational complexity aspects in modern approaches to the list coloring problem

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)