Complexity of unique list colorability

DOI10.1016/j.tcs.2008.03.018zbMath1146.05314OpenAlexW2123506360MaRDI QIDQ935144

Dániel Marx

Publication date: 31 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.03.018

zbMATH Keywords

complexitygraph coloringpolynomial hierarchylist coloringunique coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

On uniquely \(k\)-list colorable planar graphs, graphs on surfaces, and regular graphs ⋮ Note on property \(M(k)\) of some complete multipartite graphs

Cites Work

• NP is as easy as detecting unique solutions
• The complexity of planar graph choosability
• On the unique satisfiability problem
• Graph colorings with local constraints -- a survey
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of unique list colorability