Exact complexity of exact-four-colorability
From MaRDI portal
Publication:1014384
DOI10.1016/S0020-0190(03)00229-1zbMATH Open1175.68191OpenAlexW2163790508MaRDI QIDQ1014384FDOQ1014384
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
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
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Some simplified NP-complete graph problems
- The complexity of facets (and some facets of complexity)
- More complicated questions about maxima and minima, and some closures of NP
- Bounded Query Classes
- The difference and truth-table hierarchies for NP
- The Boolean Hierarchy I: Structural Properties
- Bounded queries to SAT and the Boolean hierarchy
- The Boolean Hierarchy II: Applications
- Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- On the hardness of approximating the chromatic number
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
Cited In (6)
- 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
- Title not available (Why is that?)
- Manipulation in communication structures of graph-restricted weighted voting games
- Complexity of Stability.
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)
