ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-036 | 17th March 2006 00:00

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

RSS-Feed




Revision #1
Authors: Tobias Riege, Jörg Rothe
Accepted on: 17th March 2006 00:00
Downloads: 1120
Keywords: 


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.


Paper:

TR06-036 | 7th February 2006 00:00

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





TR06-036
Authors: Tobias Riege, Jörg Rothe
Publication: 17th March 2006 05:21
Downloads: 1099
Keywords: 


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.



ISSN 1433-8092 | Imprint