scientific article; zbMATH DE number 3890729

MaRDI QIDQ3347294zbMATHFDO

Authors Hsi-Lin Sung

Publication date 1984

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)

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

Cited in

(10)

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

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)