scientific article; zbMATH DE number 3890729

zbMATH Open0558.68037MaRDI QIDQ3347294FDOQ3347294

Authors: Hsi-Lin Sung 

Publication date: 1984

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 4024813
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• On unique graph 3-colorability and parsimonious reductions in the plane
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• Exact complexity of exact-four-colorability

zbMATH Keywords

chromatic numberintractabilityDPcritical-colorabilitynondeterministic polynomial time many-one reductionsNP-complete oracleunique-colorability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (10)

• On unique graph 3-colorability and parsimonious reductions in the plane
• Exact complexity of exact-four-colorability
• Not all simple looking degree sequence problems are easy
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• Title not available (Why is that?)
• Easy intruder deduction problems with homomorphisms
• NP for Combinatorialists
• Title not available (Why is that?)
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete

This page was built for publication:

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