Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Rothe, Jörg License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-1059
URL:

Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy

pdf-format:


Abstract

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.

BibTeX - Entry

@InProceedings{rothe:DSP:2005:105,
  author =	{J{\"o}rg Rothe},
  title =	{Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2005},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  number =	{04421},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/105},
  annote =	{Keywords: Exact Colorability , exact domatic number , boolean hierarchy completeness}
}

Keywords: Exact Colorability , exact domatic number , boolean hierarchy completeness
Seminar: 04421 - Algebraic Methods in Computational Complexity
Related Scholarly Article:
Issue date: 2005
Date of publication: 2005


DROPS-Home | Fulltext Search | Imprint Published by LZI