License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.04421.2
URN: urn:nbn:de:0030-drops-1059
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/105/
Go to the corresponding Portal

Rothe, Jörg

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

pdf-format:
04421.RotheJoerg.Paper.105.pdf (0.3 MB)

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:DagSemProc.04421.2,
  author =	{Rothe, J\"{o}rg},
  title =	{{Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/105},
  URN =		{urn:nbn:de:0030-drops-1059},
  doi =		{10.4230/DagSemProc.04421.2},
  annote =	{Keywords: Exact Colorability , exact domatic number , boolean hierarchy completeness}
}

Keywords: Exact Colorability , exact domatic number , boolean hierarchy completeness
Collection: 04421 - Algebraic Methods in Computational Complexity
Issue Date: 2005
Date of publication: 24.03.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI