Exact complexity of exact-four-colorability
From MaRDI portal
Publication:1014384
DOI10.1016/S0020-0190(03)00229-1zbMath1175.68191OpenAlexW2163790508MaRDI QIDQ1014384
Publication date: 28 April 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00229-1
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (5)
On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ DP-Complete Problems Derived from Extremal NP-Complete Properties ⋮ Manipulation in communication structures of graph-restricted weighted voting games ⋮ Complexity of stability ⋮ Complexity of Stability.
Cites Work
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- More complicated questions about maxima and minima, and some closures of NP
- Bounded queries to SAT and the Boolean hierarchy
- Some simplified NP-complete graph problems
- Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- Bounded Query Classes
- The difference and truth-table hierarchies for NP
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- A relationship between difference hierarchies and relativized polynomial hierarchies
- On the hardness of approximating the chromatic number
This page was built for publication: Exact complexity of exact-four-colorability
