In their excellent paper, C.H. Papadimitriou and M. Yannakakis [PY] asked whether the minimal-3-uncolorability problem is, among other Critical Problems, $D_{p}$-complete. This paper gives an affirmative answer to the above question. We show that minimal-$k$-uncolorability is $D_{p}$-complete, for all fixed $k \geq 3$. Furthermore, for $k$ = 3, the reduction can be modified by using "sensitive" gadgets to resolve the planar case, bounded vertex degree case and their combination.