Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MINIMAL UNCOLORABILITY:
Reports tagged with minimal uncolorability:
TR06-036 | 7th February 2006
Tobias Riege, Jörg Rothe

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems

Revisions: 1

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>




ISSN 1433-8092 | Imprint