On unique graph 3-colorability and parsimonious reductions in the plane

DOI10.1016/j.tcs.2004.02.003zbMath1043.05043OpenAlexW2037855784MaRDI QIDQ596079

Régis Barbanchon

Publication date: 10 August 2004

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

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

zbMATH Keywords

Computational complexity3-ColorabilityParsimonious equivalence to SATPlanar combinatorial problemsUnique solution problems

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Some observations on holographic algorithms ⋮ Coloring invariants of knots and links are often intractable ⋮ Computational complexity and 3-manifolds and zombies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• NP is as easy as detecting unique solutions
• Sorting, linear time and the satisfiability problem
• Complexity of generalized satisfiability counting problems
• Hard Enumeration Problems in Geometry and Combinatorics
• Planar Formulae and Their Uses
• Linear time transformations between combinatorial problems
• The Complexity of Planar Counting Problems
• On generating all solutions of generalized satisfiability problems

This page was built for publication: On unique graph 3-colorability and parsimonious reductions in the plane