Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 12 / Issue 5

available in:   PDF (280 kB) PS (240 kB)
Similar Docs BibTeX   Write a comment
Links into Future


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

Tobias Riege (Heinrich-Heine-University Düsseldorf, Germany)

Jörg Rothe (Heinrich-Heine-University Düsseldorf, Germany)

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

Categories: F.1.2, F.1.3, F.2.2, F.2.3