2026-07-20T05:09:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:105 2024-03-06T11:06:00Z ddc:004 open_access

Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy Rothe, Jörg Exact Colorability exact domatic number boolean hierarchy completeness This talk 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. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with exactly four colors. DP is the second level of the boolean hierarchy. This result solves a question raised by Wagner in his 1987 TCS paper; its proof uses a clever reduction by Guruswami and Khanna. Similar results on various versions of the exact domatic number problem are also discussed. The result on Exact-Four-Colorability appeared in IPL, 2003. The results on exact domatic number problems, obtained jointly with Tobias Riege, are to appear in TOCS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jörg Rothe 2005 Is Part Of Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.04421.2 urn:nbn:de:0030-drops-1059 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04421.2 eng https://creativecommons.org/licenses/by/4.0/legalcode