Algorithmic complexity of list colorings

DOI10.1016/0166-218X(94)90150-3zbMath0807.68055MaRDI QIDQ1327214

Zsolt Tuza, Jan Kratochvíl

Publication date: 18 July 1994

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

zbMATH Keywords

Boolean satisfiabilitylist coloring problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (22)

List coloring in the absence of two subgraphs ⋮ A not 3-choosable planar graph without 3-cycles ⋮ List homomorphisms of graphs with bounded degrees ⋮ The complexity of planar graph choosability ⋮ Choosability with union separation ⋮ Conservative constraint satisfaction re-revisited ⋮ List homomorphism: beyond the known boundaries ⋮ 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart ⋮ Consensus models: computational complexity aspects in modern approaches to the list coloring problem ⋮ Precoloring Extension III: Classes of Perfect Graphs ⋮ Amenable colorings ⋮ Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7 ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ Graph isomorphism restricted by lists ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly ⋮ Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Extension problems with degree bounds ⋮ On the complexity of \(H\)-colouring planar graphs ⋮ Weighted coloring: further complexity and approximability results ⋮ Complexity of choosing subsets from color sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List colourings of planar graphs
• A simplified NP-complete satisfiability problem
• Colorings and orientations of graphs
• Precoloring extension. I: Interval graphs
• Some simplified NP-complete graph problems
• Every planar graph is 5-choosable
• The complexity of induced minors and related problems
• Planar Formulae and Their Uses
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

This page was built for publication: Algorithmic complexity of list colorings