JUCS - Journal of Universal Computer Science 12(5): 551-578, doi: 10.3217/jucs-012-05-0551
Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey
expand article infoTobias Riege‡, Jörg Rothe‡
‡ Heinrich-Heine-University Düsseldorf, Germany

Corresponding author: Tobias Riege ( riege@cs.uni-duesseldorf.de )

© Tobias Riege, Jörg Rothe.
This article is freely available under the J.UCS Open Content License.
Citation: Riege T, Rothe J (2006) Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey. JUCS - Journal of Universal Computer Science 12(5): 551-578. https://doi.org/10.3217/jucs-012-05-0551
Open Access
Abstract
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 exactly four colors, where DP is the second level of the boolean hierarchy. This result solves a question raised by Wagner in 1987, and its proof uses a clever reduction due to Guruswami and Khanna. Another result covered is due to Cai and Meyer: The graph minimal uncolorability problem is also DP-complete. Finally, similar results on various versions of the exact domatic number problem are discussed.
Keywords
Boolean hierarchy, completeness, exact colorability, exact domatic number, minimal uncolorability