Exact complexity of exact-four-colorability

DOI10.1016/S0020-0190(03)00229-1MaRDI QIDQ1014384zbMATH OpenOpenAlexFDO

Authors Jörg Rothe

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

zbMATH Keywords

computational complexitycompletenessBoolean hierarchygraph colorability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 3890729
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the hardness of approximating the chromatic number
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• Some results concerning the complexity of restricted colorings of graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Bounded Query Classes
• Bounded queries to SAT and the Boolean hierarchy
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• More complicated questions about maxima and minima, and some closures of NP
• On the hardness of approximating the chromatic number
• Some simplified NP-complete graph problems
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The complexity of facets (and some facets of complexity)
• The difference and truth-table hierarchies for NP
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

Cited in

(6)

• Complexity of Stability.
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• Complexity of stability
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• scientific article; zbMATH DE number 3890729 (Why is no real title available?)
• Manipulation in communication structures of graph-restricted weighted voting games

This page was built for publication: Exact complexity of exact-four-colorability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014384)