Exact complexity of exact-four-colorability
type: Item
instance of: scholarly article
title: Exact complexity of exact-four-colorability
zbMATH Open document ID: 1175.68191
DOI: 10.1016/S0020-0190(03)00229-1
author: Jörg Rothe
published in: Information Processing Letters
publication date: 2009-04-28T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5547770
zbMATH Keywords: computational complexity
zbMATH Keywords: graph colorability
zbMATH Keywords: completeness
zbMATH Keywords: Boolean hierarchy
MaRDI profile type: Publication
cites work: A relationship between difference hierarchies and relativized polynomial hierarchies
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: The Boolean Hierarchy I: Structural Properties
cites work: The Boolean Hierarchy II: Applications
cites work: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
cites work: Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
cites work: Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: On the hardness of approximating the chromatic number
cites work: The difference and truth-table hierarchies for NP
cites work: The complexity of facets (and some facets of complexity)
cites work: Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
cites work: More complicated questions about maxima and minima, and some closures of NP
cites work: Bounded Query Classes
full work available at URL: s0020-0190(03)00229-1
OpenAlex ID: W2163790508
description: scientific article; zbMATH DE number 5547770