On the Complexity of Graph Critical Uncolorability. - Jin-yi Cai; Gabriele E. Meyer (ICALP, 1987)

Graph Minimal Uncolorability is D^P-Complete. - Jin-yi Cai; Gabriele E. Meyer (SIAM J. Comput., 1987)