ECCC-Report TR06-036https://eccc.weizmann.ac.il/report/2006/036Comments and Revisions published for TR06-036en-usFri, 17 Mar 2006 05:21:16 +0200
Paper TR06-036
| Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems |
Tobias Riege,
Jörg Rothe
https://eccc.weizmann.ac.il/report/2006/036This 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.
Fri, 17 Mar 2006 05:21:16 +0200https://eccc.weizmann.ac.il/report/2006/036
Revision 1
| Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems |
Tobias Riege,
Jörg Rothe
https://eccc.weizmann.ac.il/report/2006/036#revision1This 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.
Fri, 17 Mar 2006 00:00:00 +0200https://eccc.weizmann.ac.il/report/2006/036#revision1