Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete

DOI10.1137/0216022zbMath0626.05017OpenAlexW1806792047WikidataQ59795792 ScholiaQ59795792MaRDI QIDQ3029023

Jin-Yi Cai, Gabriele E. Meyer

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216022

zbMATH Keywords

graph coloringNP-completenessplanar graph coloring\(D^ P\)-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

DP-Complete Problems Derived from Extremal NP-Complete Properties, More complicated questions about maxima and minima, and some closures of NP, Intersection suffices for Boolean hierarchy equivalence, Complexity of stability, Complexity of Stability., Exact complexity of exact-four-colorability, Finding Optimal Solutions With Neighborly Help.