Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
Jin‐Yi Cai, Gabriele E. Meyer · SIAM Journal on Computing · 1987
In their excellent paper, C. H. Papadimitriou and M. Yannakakis [J. Comput. System Sci., 28 (1982), pp. 244–259] asked whether the minimal-3-uncolorability problem is, among other Critical Problems, DP-complete. This paper gives an affirmative answer to the above question. We show that minimal-k-uncolorability is ${\text{D}}^{\text{p}} $-complete, for all fixed $k \geqq 3$. Furthermore, for $k = 3$, the reduction can be modified by using “sensitive” gadgets to resolve the planar case.