Exact Complexity of Exact-Four-Colorability
J\"{o}rg Rothe\thanks{This work was supported in part by grant NSF-INT-9815095/DAAD-315-PPP-g\"{u}-ab and by a Hei\-sen\-berg Fellowship of the Deut\-sche For\-schungs\-ge\-mein\-schaft.}
Abteilung f\"ur Informatik
Heinrich-Heine-Universit\"at D\"usseldorf
40225 D\"usseldorf
Germany
Let $M_k \seq \nats$ be a given set that consists of $k$ noncontiguous integers. Define $\exactcolor{M_k}$ to be the problem of determining whether~$\chi(G)$, the chromatic number of a given graph~$G$, equals one of the $k$ elements of the set $M_k$ exactly. In 1987, Wagner~\cite{wag:j:min-max} proved that $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete, where $M_k = \{6k+1, 6k+3, \ldots, 8k-1 \}$ and $\bhlevel{2k}$ is the $2k$th level of the boolean hierarchy over~$\np$. In particular, for $k = 1$, it is DP-complete to determine whether $\chi(G) = 7$, where $\DP = \bhlevel{2}$. Wagner raised the question of how small the numbers in a $k$-element set $M_k$ can be chosen such that $\exactcolor{M_k}$ still is $\bhlevel{2k}$-complete. In particular, for $k = 1$, he asked if it is DP-complete to determine whether $\chi(G) = 4$. % In this note, we solve this question of Wagner and determine the precise threshold $t \in \{4, 5, 6, 7\}$ for which the problem $\exactcolor{\{t\}}$ jumps from NP to DP-completeness: It is DP-complete to determine whether $\chi(G) = 4$, yet $\exactcolor{\{3\}}$ is in~$\np$. More generally, for each $k \geq 1$, we show that $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete for $M_k = \{3k+1, 3k+3, \ldots, 5k-1 \}$.
main.tex

\documentclass[11pt]{article}
\emergencystretch=2em

\usepackage{times}
\usepackage{eepic,epic}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsopn}
\usepackage{graphicx}
%

%

%
\makeatletter%
\def\nottoobig#1{{\hbox{$\left#1\vcenter to1.111\ht\strutbox{}\right.\n@space$}}}
\makeatother%

%
%
%
%
%
%
\makeatother%

%
%
%
%

%

\makeatletter%

%
%
%
%
\newcount\hour  \newcount\minutes  \hour=\time  \divide\hour by 60
\minutes=\hour  \multiply\minutes by -60  \advance\minutes by \time
\def\mmmddyyyy{\ifcase\month\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or Jul\or
  Aug\or Sep\or Oct\or Nov\or Dec\fi \space\number\day, \number\year}
\def\hhmm{\ifnum\hour<10 0\fi\number\hour :%
  \ifnum\minutes<10 0\fi\number\minutes}
\def\Draft{{\it Draft of \mmmddyyyy}}

%
%
\topsep 8pt plus2pt minus4pt   %

%
%
%

%
%
%

%
%
%

%
%
%
%

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
\def\ps@jtsheadings{%
\def\@oddhead{\it\rightmark\hfil\rm\thepage}%
\def\@oddfoot{\hfil\Draft}%
\if@twoside%
\def\@evenhead{\rm\thepage\hfil\it\leftmark}%
\def\@evenfoot{\Draft\hfil}%
\else
\let\@evenhead\@oddhead%
\let\@evenfoot\@oddfoot%
\fi%
}
\def\ps@jtsplain{%
\def\@oddhead{\hfil\Draft}%
\def\@oddfoot{\hfil\rm\thepage\hfil}%
\let\@evenfoot\@oddfoot%
\if@twoside \def\@evenhead{\Draft\hfil} \else \let\@evenhead\@oddhead \fi
}

%
%
%
\def\chaptermark#1{\markboth{\thechapter.\ #1}{\thechapter.\ #1}}%
\def\sectionmark#1{\markright{\thesection.\ #1}}
\def\subsectionmark#1{\markright{\thesubsection.\ #1}}
\def\subsubsectionmark#1{\markright{\thesubsubsection.\ #1}}

%
%
%
%
\def\section{\@startsection {section}{1}{\z@}
    {3.5ex plus1ex minus.2ex}{2.3ex plus.2ex}{\Large\bf}}
\def\subsection{\@startsection{subsection}{2}{\z@}
    {3.25ex plus1ex minus.2ex}{1.5ex plus.2ex}{\large\bf}}
\def\subsubsection{\@startsection{subsubsection}{3}{\z@}
    {3.25ex plus1ex minus.2ex}{1.5ex plus.2ex}{\normalsize\bf}}
\def\paragraph{\@startsection{paragraph}{4}{\z@}
    {3.25ex plus1ex minus.2ex}{1em}{\normalsize\bf}}
\def\subparagraph{\@startsection{subparagraph}{4}{\parindent}
    {3.25ex plus1ex minus.2ex}{1em}{\normalsize\bf}}

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
\makeatother%


%
%
%
%
%
%
%
%
\makeatletter \@beginparpenalty=10000 \makeatother
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%


%
%

\def\underl#1 {\leavevmode\let\first=\relax\underli #1 }
\def\underli#1 {\ifx&#1\let\next=\relax\unskip
                \else\let\next=\underli\first\ulinebox{#1}\fi\let\first=\undersp\next}
\def\undersp{\penalty50\ulinebox{\space}\penalty50}
\def\ulinebox#1{\vtop{\hbox{\strut#1}\hrule}}%
\def\unice#1 {\underl #1 & }
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%



%
%
%
%
%
%
%
\def\desclabel#1{\bf #1\hfil}
\def\desc{\list{}{%
\labelwidth=\leftmargin
\advance \labelwidth by -\labelsep
\let \makelabel=\desclabel}}
\let\enddesc=\endlist




%

\makeatletter %
\renewcommand{\theequation}{\thesection.\arabic{equation}}
%
%
%
\newcommand{\band}{\bigwedge}
\newcommand{\Band}[3]{(\bigwedge#1\!\!:\,#2\!\!:\,#3)}
\newcommand{\bor}{\bigvee}
\newcommand{\Bor}[3]{(\bigvee#1\!\!:\,#2\!\!:\,#3)}
\newcommand{\Forall}[3]{(\forall #1\!\!:\,#2\!\!:\,#3)}
\newcommand{\Exists}[3]{(\exists #1\!\!:\,#2\!\!:\,#3)}
\newcommand{\Union}[3]{(\bigcup #1\!\!:\,#2\!\!:\,#3)}
%
%
%
%
%
%
\def\union{\,\bigcup\limits\,}
\def\inter{\,\bigcap\limits\,}
\newcommand{\true}{\mbox{\it true}}
\newcommand{\false}{\mbox{\it false}}
\newcommand{\SUM}[3]{ (\sum #1 \!\! : \, #2 \!\!:\, #3) }
\newcommand{\IFS}{\mbox{\bf if}}
\newcommand{\IF}[1]{ \mbox{\bf if} \, #1 \, \rightarrow \, }
\newcommand{\GC}[2]{ #1 \, \rightarrow \, #2 }
\newlength{\filength}
\settowidth{\filength}{\mbox{\bf f{}i}}
\newsavebox{\gcbox}
\sbox{\gcbox}{\framebox[\filength]{\rule{0ex}{2ex}}}
\newcommand{\BB}[1]{\usebox{\gcbox}\; #1 \, \rightarrow \, }
\newcommand{\FI}{\; \mbox{\bf f{}i}}
\newcommand{\Skip}{ \mbox{\bf skip} }
\newcommand{\DOS}{\mbox{\bf do}}
\newcommand{\DO}[1]{\mbox{\bf do} \, #1 \, \rightarrow \,}
\newcommand{\OD}{\mbox{\bf od}}
\newcommand{\cobegin}{{\bf cobegin}\,}
%
\newcommand{\coend}{\,{\bf coend}}
\newcommand{\Set}[1]{ \hbox{\bf\{} #1 \hbox{\bf\}}}
\newcommand{\Bag}[1]{ \{\!| #1  |\!\}}
%
%
%
%
%
%
%
\newlength{\leftjustindent}
\newlength{\@leftjustindent}
\setlength{\@leftjustindent}{\leftmargin}
\def\leftjust{\let\\\@leftjustcr\let\end\@endleftjust
  \addtolength{\@leftjustindent}{\leftjustindent}
  \vcenter\bgroup
  \halign\bgroup
    \hbox to\displaywidth{
      \rule{\@leftjustindent}{0ex}$\displaystyle##$\hfill
      }\crcr
}
\def\endleftjust{\crcr\egroup\egroup\endgroup}
\def\@endleftjust#1{\crcr\egroup\egroup\@checkend{#1}\endgroup}
\def\@leftjustcr{\crcr}

\newcommand{\hoare}[3]{\{{#1}\}\:{#2}\:\{{#3}\}}
\renewcommand{\wp}[2]{ {\it wp}({#1},{#2})}
\newcommand{\assert}[1]{\!\{#1\}}
\newcommand{\atom}[1]{\langle\,{#1}\,\rangle}
\newcommand{\lbl}[1]{{#1 \!:\;\,}}
\newcommand{\pre}[1]{ {\it pre}({#1})}
\newcommand{\post}[1]{ {\it post}({#1}) }
\newcommand{\NI}[2]{ {\it NI}({#1},{#2}) }
\newcommand{\equi}[3]{ {  {\rm E}_{#1}^{#2}({#3}) }    }
\newcommand{\red}[3]{ {  {\rm R}_{#1}^{#2}({#3}) }    }
\newcommand{\sparse}{{{\rm SPARSE}}}
\newcommand{\tally}{{{\rm TALLY}}}
%
\newtheorem{theorem}{Theorem}%
\newtheorem{corollary}[theorem]{Corollary}
%
%
%
%
%
%
%
%
%
\newcommand{\qedblob}{\mbox{\rule[-1.5pt]{5pt}{10.5pt}}}
\def\literalqed{{\ \nolinebreak\hfill\mbox{\qedblob\quad}}}
\def\qedcareful{\literalqed}
\def\qed{\literalqed}
\def\trueloveqed{{\ \nolinebreak\hfill\mbox{\boldmath
\Huge$ \Box$}\nolinebreak\mbox{$\!\!\!\!\!\!
{}^{\normalsize\heartsuit}$}}}
%
%
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newcommand{\singlespacing}{\let\CS=
\@currsize\renewcommand{\baselinestretch}{1}\tiny\CS}
\newcommand{\singlespacingplus}{\let\CS=
\@currsize\renewcommand{\baselinestretch}{1.25}\tiny\CS}
\newcommand{\doublespacing}{\let\CS=
\@currsize\renewcommand{\baselinestretch}{1.75}\tiny\CS}
\newcommand{\draftspacing}{\let\CS=
\@currsize\renewcommand{\baselinestretch}{2.0}\tiny\CS}
\newcommand{\foospacing}{\let\CS=
\@currsize\renewcommand{\baselinestretch}{1.05}\tiny\CS}
\newcommand{\normalspacing}{\singlespacing}
\makeatother%


%
\hyphenation{theory theoretical area areas theorem theorems par-allel par-allelize par-allelized threshold Hemaspaan-dra}

%

%
%
%
\def\grantnumber{This work was supported, in part,
by NSF grant no.\ DCR-8320274 and Office of Naval
Research contract N00014-86-K-0092.}
%
%
%
%
\mathcode`\0="0030      %
\mathcode`\1="0031
\mathcode`\2="0032
\mathcode`\3="0033
\mathcode`\4="0034
\mathcode`\5="0035
\mathcode`\6="0036
\mathcode`\7="0037
\mathcode`\8="0038
\mathcode`\9="0039
%
%
%
%
%
%


\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{trick}[theorem]{Trick Result}


%
%
%
%
%
%

%

%
\flushbottom{}
%
\makeatletter
\clubpenalty=\@highpenalty
\widowpenalty=\@highpenalty
\makeatother

%
\let\BLS=\baselinestretch

%
%
\makeatletter
\newcommand{\niceonespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.1}\tiny\CS}\newcommand{\nicetwospacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.2}\tiny\CS}
\newcommand{\nicethreespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.3}\tiny\CS}
\newcommand{\singlespacingplusplus}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.35}\tiny\CS}
\newcommand{\nicefourspacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.4}\tiny\CS}
\newcommand{\nicefivespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.5}\tiny\CS}
\newcommand{\nicesixpacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.6}\tiny\CS}
\makeatother

%
\makeatletter
\def\@cite#1#2{[#1\if@tempswa , #2\fi]}
\makeatother

%
%
%
\makeatletter
\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi
  \def\@citea{}\@cite{\@for\@citeb:=#2\do
    {\@citea\def\@citea{,\linebreak[0]}\@ifundefined
       {b@\@citeb}{{\bf ?}\@warning
       {Citation `\@citeb' on page \thepage \space undefined}}%
\hbox{\csname b@\@citeb\endcsname}}}{#1}}
\makeatother


%
\makeatletter
\def\ps@thesis{\def\@oddhead{\hfil\rm\thepage\hfil}\def\@oddfoot{}\def\@evenhead{\hfil\rm\thepage\hfil}\def\@evenfoot{}\def\chaptermark##1{}\def\sectionmark##1{}}
\makeatother

\makeatletter
%
%
%
%
\def\foobarpt{\textfont\z@\tenrm 
  \scriptfont\z@\ninrm \scriptscriptfont\z@\sevrm
\textfont\@ne\tenmi \scriptfont\@ne\ninmi \scriptscriptfont\@ne\sevmi
\textfont\tw@\tensy \scriptfont\tw@\ninsy \scriptscriptfont\tw@\sevsy
\textfont\thr@@\tenex \scriptfont\thr@@\tenex \scriptscriptfont\thr@@\tenex
\def\unboldmath{\everymath{}\everydisplay{}\@nomath\unboldmath
          \textfont\@ne\tenmi 
          \textfont\tw@\tensy \textfont\lyfam\tenly
          \@boldfalse}\@boldfalse
\def\boldmath{\@ifundefined{tenmib}{\global\font\tenmib\@mbi\@magscale1\global
        \font\tensyb\@mbsy \@magscale1\global\font
         \tenlyb\@lasyb\@magscale1\relax\@addfontinfo\@xiipt
              {\def\boldmath{\everymath
                {\mit}\everydisplay{\mit}\@prtct\@nomathbold
                \textfont\@ne\tenmib \textfont\tw@\tensyb 
                \textfont\lyfam\tenlyb\@prtct\@boldtrue}}}{}\@xiipt\boldmath}%
\def\prm{\fam\z@\tenrm}%
\def\pit{\fam\itfam\tenit}\textfont\itfam\tenit \scriptfont\itfam\ninit
   \scriptscriptfont\itfam\sevit
\def\psl{\fam\slfam\tensl}\textfont\slfam\tensl 
     \scriptfont\slfam\tensl \scriptscriptfont\slfam\tensl
\def\pbf{\fam\bffam\tenbf}\textfont\bffam\tenbf 
   \scriptfont\bffam\ninbf \scriptscriptfont\bffam\ninbf 
\def\ptt{\fam\ttfam\tentt}\textfont\ttfam\tentt
   \scriptfont\ttfam\nintt \scriptscriptfont\ttfam\nintt 
\def\psf{\fam\sffam\tensf}\textfont\sffam\tensf
    \scriptfont\sffam\tensf \scriptscriptfont\sffam\tensf
\def\psc{\@getfont\psc\scfam\@xiipt{\@mcsc\@magscale1}}%
\def\ly{\fam\lyfam\tenly}\textfont\lyfam\tenly 
   \scriptfont\lyfam\ninly \scriptscriptfont\lyfam\sevly
 \@setstrut \rm}

\makeatother




%

%
%
%
%
%
%

\newcommand{\sharpp}{{\rm \#P}}
\newcommand{\sharpsat}{{\rm \#SAT}}
\newcommand{\sat}{\mbox{\rm SAT}}
\newcommand{\qbf}{\mbox{\rm QBF}}
\newcommand{\parityp}{{\rm \oplus P}}
\newcommand{\up}{\mbox{\rm UP}}
\newcommand{\us}{\mbox{\rm US}}
\newcommand{\fewnp}{\mbox{\rm FewNP}}
\newcommand{\fewp}{\mbox{\rm FewP}}
\newcommand{\coup}{\mbox{\rm coUP}}
\newcommand{\e}{\mbox{\rm E}}
\renewcommand{\exp}{{\rm EXP}}
\newcommand{\NE}{\mbox{\rm NE}}
\renewcommand{\ne}{\mbox{\rm NE}}
\newcommand{\nexp}{\mbox{\rm NEXP}}
\newcommand{\p}{\mbox{\rm P}}
\newcommand{\littlep}{{\rm p}}
\newcommand{\NP}{\mbox{\rm NP}}
\newcommand{\DP}{\mbox{\rm DP}}
\newcommand{\np}{\mbox{\rm NP}}
\newcommand{\nt}{\mbox{\rm NT}}
\newcommand{\nnt}{\mbox{\rm NNT}}
\newcommand{\parityoptp}{{\rm \oplus{}OptP}}
\newcommand{\optp}{{\rm OptP}}
\newcommand{\diffp}{{\rm D^P}}
\newcommand{\pp}{\mbox{\rm PP}}
\newcommand{\bpp}{\mbox{\rm BPP}}
\newcommand{\zpp}{\mbox{\rm ZPP}}
\newcommand{\cor}{\mbox{\rm coR}}
\newcommand{\npc}{$\np$-com\-plete}
\newcommand{\conp}{\mbox{\rm coNP}}
\newcommand{\pspace}{\mbox{\rm PSPACE}}
\newcommand{\eespace}{{\rm EESPACE}}
\newcommand{\dspace}{{\rm DSPACE}}
\newcommand{\psp}{{\pspace}}
\newcommand{\pnexp}{{\p^\nexp}}
\newcommand{\npnexp}{{\np^\nexp}}
\newcommand{\nenp}{{\ne^\np}}
\newcommand{\enp}{{\e^\np}}
\newcommand{\pnp}{{\p^{\rm NP}}}
\newcommand{\npnp}{{\np^{\rm NP}}}
\newcommand{\pnplog}{{\p^{\np[\log ]}}}
\newcommand{\nexpnp}{{\nexp^\np}}
\newcommand{\coNP}{{\rm coNP}}
\newcommand{\cone}{{\rm CONE}}
\newcommand{\sigmatwozero}{{\Sigma_2^0}}
\newcommand{\pitwozero}{{\Pi_2^0}}
\newcommand{\pithreezero}{{\Pi_3^0}}
\newcommand{\sigmathreezero}{{\Sigma_3^0}}
\newcommand{\sigmatwo}{{\Sigma_2^p}}
\newcommand{\sigmak}{{\Sigma_k^p}}
\newcommand{\pitwo}{{\Pi_2^p}}
\newcommand{\thetatwo}{{\Theta_2^p}}
\newcommand{\deltatwo}{{\Delta_2^p}}
\newcommand{\poly}{{\rm poly}}
\newcommand{\ph}{{\rm PH}}
\newcommand{\few}{{\rm Few}}
\newcommand{\fewch}{{\rm FewCH}}
\newcommand{\eh}{{\rm EH}}
\newcommand{\proof}{\noindent {\bf Proof.}\quad}
\def\bull{\vrule height .9ex width .8ex depth -.1ex }
%
%
%
%
%
%
\newcommand{\blob}{\mbox{\rule[-1.5pt]{5pt}{10.5pt}}}
\newcommand{\lindent}{\qquad}
\newcommand{\magicnum}{{ n^{\frac{1-\epsilon}{\epsilon}+\delta}}}
\newcommand{\fsup}{{\,f_{super}\,}}
\newcommand{\fred}{{\,f_{reduced}\,}}
\newcommand{\pne}{{\p^\ne}}
\newcommand{\npne}{{\np^\ne}}
\newcommand{\nnexarg}{{\nxx^\nexx (x) }}
\newcommand{\nnexx}{{\nxx^\nexx  }}
\newcommand{\nnex}{{\nxx^\nexx }}
\newcommand{\expnp}{{\exp^\np }}
\newcommand{\nxx}{{\rm N_{17}}}
\newcommand{\nexx}{{\rm NE_{21}}}
\newcommand{\seh}{{\rm SEH}}
\newcommand{\sexph}{{\rm SEXPH}}
\newcommand{\pstar}{{\p_\star}}
\newcommand{\nestar}{{\ne_{\,\star}}}
%
\newcommand{\supersetproper}{  \stackrel{\scriptscriptstyle\superset}{\scriptscriptstyle\not-}}
\newcommand{\subsetproper}{  \stackrel{\scriptscriptstyle\subset}{\scriptscriptstyle\not-}}
%
%
%
%
%
%
%
\newcommand{\superset}{\supset}
\newcommand{\superseteq}{\supseteq}

\def\unionfromc{\,\textstyle\bigcup_{\scriptstyle c}\,}
\def\unionfromk{\,\textstyle\bigcup_{\scriptstyle k}\,}









%
%
\newcommand{\newlozenge}{\setlength{\fboxsep}{0pt}\setlength{\fboxrule}{.7pt}\framebox[6pt]{\rule{0pt}{9pt}}}

%
%

%


%
%
%
%
\def\pair#1{{{\langle\!\!~#1~\!\!\rangle}}}
\def\pairs#1{{{\langle\!\!~#1~\!\!\rangle}}}
\newcommand{\piso}{\mbox{$\littlep$-iso\-mor\-phic}}
\newcommand{\manyonea}{\mbox{$\,\leq_{\rm m}^{{\littlep},\,A}\,$}}
\newcommand{\manyone}{\mbox{$\,\leq_{\rm m}^{{\littlep}}$\,}}
\newcommand{\paiso}{\mbox{$\littlep^A$-iso\-mor\-phic}}
\newcommand{\pisoa}{\paiso}
\newcommand{\pisoam}{\mbox{$\littlep^A$-iso\-mor\-phism}}
\newcommand{\pisom}{\mbox{$\littlep$-iso\-mor\-phism}}
\newcommand{\pselective}{\mbox{$\p$-selec\-tive}}
\newcommand{\sigmastar}{\mbox{$\Sigma^\ast$}}
\newcommand{\pisnp}{\mbox{$\p=\np$}}
\newcommand{\usuba}{\mbox{$U_A$}}
\newcommand{\univsuba}{\mbox{$Univ_A$}}
\newcommand{\pisnotnp}{\mbox{$\p\neq\np$}}
\newcommand{\lb}{\mbox{\{}}
\newcommand{\rb}{\mbox{\}}}
\newcommand{\pa}{\mbox{$\p^A$}}
\newcommand{\calf}{\mbox{$\cal F$}}
\newcommand{\calc}{\mbox{$\cal C$}}
\newcommand{\dr}{{\tt DodgsonRanking}}
\newcommand{\dw}{{\tt DodgsonWinner}}
\newcommand{\kw}{{\tt KemenyWinner}}
\newcommand{\score}{{\mbox{\it{}Score}}}
\newcommand{\dsum}{{\mbox{\it{}DodgsonSum}}}
\newcommand{\ds}{{\tt DodgsonScore}}
\newcommand{\xthreec}{{\tt ExactCoverByThreeSets}}
\newcommand{\satisfiability}{{\tt Satisfiability}}
\newcommand{\clique}{{\tt Clique}}
\newcommand{\threedm}{{\tt ThreeDimensionalMatching}}
\newcommand{\merge}{\mbox{\it{}Merge}}
\newcommand{\mergeprime}{\mbox{{\it{}Merge}$'$}}
\newcommand{\ncertifiesdefeat}{{\tt CertifiesTieOrDefeat}}
\newcommand{\specialdpproblem}{{\tt SpecialProblem}}

\newcommand{\kcolor}{{{\tt \mbox{K-}Colorability}}}
\newcommand{\threecolor}{{{\tt 3\mbox{-}Colorability}}}
\newcommand{\algthreecolor}{{{\tt A\mbox{-}3\mbox{-}Colorability}}}

\newcommand{\ddseqthreecolor}{{{\tt DD\mbox{-}SEQ\mbox{-}3\mbox{-}Colorability}}}
\newcommand{\slseqthreecolor}{{{\tt SL\mbox{-}SEQ\mbox{-}3\mbox{-}Colorability}}}

\newcommand{\ddseqint}{{{\tt DD\mbox{-}SEQINT}}}
\newcommand{\slseqint}{{{\tt SL\mbox{-}SEQINT}}}

\newcommand{\threesat}{{{\tt 3\mbox{-}SAT}}}

\newcommand{\voter}{\pair}
\newcommand{\npa}{\mbox{$\np^A$}}
\newcommand{\conpa}{\mbox{$\conp^A$}}
\newcommand{\upa}{\mbox{$\up^A$}}
\newcommand{\sparses}{\mbox{ sparse $S\,$}}
\newcommand{\bigo}{\mbox{$\cal O$}}
\newcommand{\condition}{\,\nottoobig{|}\:}
\def\land{{\; \wedge \;}}


%
%

\newcommand{\parallelnp}{\mbox{$\p_{||}^{\np}$}}
\newcommand{\mis}{\mbox{\it mis}}
\newcommand{\mdg}{\mbox{\it mdg}}
\newcommand{\misequals}{\mbox{\tt MIS$_{\mbox{\footnotesize\tt equal}}$}}
\newcommand{\sone}{\mbox{${\cal S}_1$}}
\newcommand{\ar}{\mbox{${\cal A}_r$}}
\newcommand{\sr}{\mbox{${\cal S}_r$}}
\newcommand{\truthtable}{\mbox{$\,\leq_{\rm tt}^{{\littlep}}$\,}}
\newcommand{\turing}{\mbox{$\,\leq_{\rm T}^{{\littlep}}$\,}}

\def\bhlevel#1{{{\mbox{\rm{}BH}_{#1}(\np)}}}
\newcommand{\bhnp}{{{\mbox{\rm{}BH}(\np)}}}
\def\exactcolor#1{{\tt{}Exact}\mbox{-}{#1}\mbox{-}{\tt{}Colorability}}
\newcommand{\exactfourcolor}{{\tt{}Exact}\mbox{-}{\tt{}Four}\mbox{-}{\tt{}Colorability}}

\newcommand\seq{\subseteq}
\renewcommand\.{\cdot}
\newcommand\<{\langle}
\renewcommand\>{\rangle}
\newcommand\la{\ \leftarrow \ }
\newcommand\ra{\ \rightarrow \ }
\newcommand\lra{\ \leftrightarrow \ }
\newcommand\La{\ \Leftarrow \ }
\newcommand\Ra{\ \Rightarrow \ }
\newcommand\Lra{\ \Leftrightarrow \ }
\newcommand\lola{\ \longleftarrow \ }
\newcommand\lora{\ \longrightarrow \ }
\newcommand\lolra{\ \longleftrightarrow \ }
\newcommand\Lola{\ \Longleftarrow \ }
\newcommand\Lora{\, \Longrightarrow \ }
\newcommand\Lolra{\ \Longleftrightarrow \ }
\newcommand\Lolradef{\ :\Longleftrightarrow \ }

\newcommand{\naturalnumber}{\ensuremath{{  \mathbb{N} }}}
\def\nats{\naturalnumber}

%

%
%
%


%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%


\newenvironment{construction}{\bigbreak\begin{block}}{\end{block}
    \bigbreak}

\newenvironment{block}{\begin{list}{\hbox{}}{\leftmargin 1em
    \itemindent -1em \topsep 0pt \itemsep 0pt \partopsep 0pt}}{\end{list}}


%
%
%
%
%
%
%
%

\dimen15=0.75em
\dimen16=0.75em

\newcommand{\lblocklabel}[1]{\rlap{#1}\hss}

\newenvironment{lblock}{\begin{list}{}{\advance\dimen15 by \dimen16
    \leftmargin \dimen15
    \itemindent -1em
    \topsep 0pt
    \labelwidth 0pt
    \labelsep \leftmargin
    \itemsep 0pt
    \let\makelabel\lblocklabel
    \partopsep 0pt}}{\end{list}}


%
%

\newenvironment{lconstruction}[2]{\dimen15=#1 \dimen16=#2
  \bigbreak\begin{block}}{\end{block}\bigbreak}


\newcommand{\Comment}[1]{{\sl (\  #1\ )}}


%
%
%

%




%
%
%
\title{Exact Complexity of Exact-Four-Colorability}

\author{
J\"{o}rg Rothe\thanks{This work was
supported in part by grant NSF-INT-9815095/DAAD-315-PPP-g\"{u}-ab
and by a Hei\-sen\-berg Fellowship
of the Deut\-sche For\-schungs\-ge\-mein\-schaft.} \\ 
Abteilung f\"ur Informatik \\
Heinrich-Heine-Universit\"at D\"usseldorf \\
40225 D\"usseldorf, Germany \\
${\tt rothe@cs.uni\mbox{-}duesseldorf.de}$
}

%
\date{September 14, 2001}


%
%
%
%


%
%
%
\lefthyphenmin=100

%
%
%

\setlength{\oddsidemargin}{0.25in}
\setlength{\evensidemargin}{\oddsidemargin}
\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\topmargin}{-0.0in}

%
%
%
%
%
%

%
%
%
%
%
%
%
%
%
%
%
%



%
%
%
%
%
%
%
%

%
%
%
%
%
%
%
%
%
\makeatletter
\def\@listI{\leftmargin\leftmargini \parsep 4.5pt plus 1pt minus 1pt\topsep
6pt plus 2pt minus 2pt \itemsep  2pt plus 2pt minus 1pt}

\let\@listi\@listI
\@listi
\makeatother


\begin{document}

%
%
%
%
%
\typeout{WARNING:  BADNESS used to suppress reporting!  Beware!!}
\hbadness=3000%
\vbadness=10000 %






%
%
%
\bibliographystyle{alpha}

%
\pagestyle{empty}
%
%
%
%
%
%
%
%
\setcounter{page}{1}


%

\sloppy

%
\pagestyle{empty}
\setcounter{footnote}{0}
%

\maketitle

%
%
%

%
%
\begin{abstract}
  Let $M_k \seq \nats$ be a given set that consists of $k$ noncontiguous
  integers.  Define $\exactcolor{M_k}$ to be the problem of determining
  whether~$\chi(G)$, the chromatic number of a given graph~$G$, equals
  one of the $k$ elements of the set $M_k$ exactly.  In 1987,
  Wagner~\cite{wag:j:min-max} proved that $\exactcolor{M_k}$ is
  $\bhlevel{2k}$-complete, where $M_k = \{6k+1, 6k+3, \ldots, 8k-1 \}$ and
  $\bhlevel{2k}$ is the $2k$th level of the boolean hierarchy over~$\np$.  In
  particular, for $k = 1$, it is DP-complete to determine whether $\chi(G) =
  7$, where $\DP = \bhlevel{2}$.  Wagner raised the question of how small the
  numbers in a $k$-element set $M_k$ can be chosen such that
  $\exactcolor{M_k}$ still is $\bhlevel{2k}$-complete.  In particular, for $k
  = 1$, he asked if it is DP-complete to determine whether $\chi(G) = 4$.
%
  In this note, we solve this question of Wagner and determine the precise
  threshold $t \in \{4, 5, 6, 7\}$ for which the problem $\exactcolor{\{t\}}$
  jumps from NP to DP-completeness: It is DP-complete to determine whether
  $\chi(G) = 4$, yet $\exactcolor{\{3\}}$ is in~$\np$.  More generally, for
  each $k \geq 1$, we show that $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete
  for $M_k = \{3k+1, 3k+3, \ldots, 5k-1 \}$.
\end{abstract}

%

%
%
%
%
%
%
\setcounter{page}{1}
%
%
\pagestyle{plain}
%
\sloppy


\section{\boldmath{Exact-$M_k$-Colorability} and the Boolean Hierarchy over NP}

To classify the complexity of problems known to be NP-hard or coNP-hard, but
seemingly not contained in $\np \cup \conp$, Papadimitriou and
Yannakakis~\cite{pap-yan:j:dp} introduced~DP, the class of differences of two
NP problems.  They showed that DP contains various interesting types of
problems, including {\em uniqueness problems}, {\em critical graph problems},
and {\em exact optimization problems}.  For example, Cai and
Meyer~\cite{cai-mey:j:dp} proved the DP-completeness of
${\tt{}Minimal}\mbox{-}3\mbox{-}{\tt{}Uncolorability}$, a critical graph
problem that asks whether a given graph is not 3-colorable, but deleting any
of its vertices makes it 3-colorable.  A graph is said to be {\em
  $k$-colorable\/} if its vertices can be colored using no more than $k$
colors such that no two adjacent vertices receive the same color.  The {\em
  chromatic number of a graph~$G$}, denoted~$\chi(G)$, is defined to be the
smallest $k$ such that $G$ is $k$-colorable.

Generalizing~DP, Cai et
al.~\cite{cai-gun-har-hem-sew-wag-wec:j:bh1,cai-gun-har-hem-sew-wag-wec:j:bh2}
defined and studied the boolean hierarchy over~$\np$.  Their papers initiated
an intensive work and many papers on the boolean hierarchy;
e.g.,~\cite{wag:j:min-max,koe-sch-wag:j:diff,kad:joutdatedbychangkadin:bh,wag:j:bounded,bei:j:bounded-queries,cha:thesis,hem-rot:j:boolean}
%
to name just a few.
To define the boolean hierarchy, we use the symbols $\wedge$ and~$\vee$,
respectively, to denote the {\em complex intersection\/} and the {\em complex
  union\/} of set classes. That is, for classes $\mathcal{C}$ and
$\mathcal{D}$ of sets, define
\begin{eqnarray*}
\mathcal{C} \wedge \mathcal{D} & = &
\{ A \cap B \mid A \in \mathcal{C} \mbox{ and } B \in \mathcal{D}\}; \\ 
\mathcal{C} \vee \mathcal{D} & = &
\{ A \cup B \mid A \in \mathcal{C} \mbox{ and } B \in \mathcal{D}\}.
\end{eqnarray*}

\begin{definition} {\rm{}(\cite{cai-gun-har-hem-sew-wag-wec:j:bh1})}\quad
The {\em boolean hierarchy over $\np$\/} is inductively defined as follows:
\begin{eqnarray*}
\bhlevel{1} & = & \np, \\
\bhlevel{2} & = &  \np \wedge \conp, \\
\bhlevel{k} & = &  \bhlevel{k-2} \vee \bhlevel{2} 
                   \mbox{\quad for $k \geq 3$, and} \\
\bhnp & = &  \bigcup_{k \geq 1} \bhlevel{k}.
\end{eqnarray*}
\end{definition}

Equivalent definitions in terms of different boolean hierarchy normal forms
can be found in the
papers~\cite{cai-gun-har-hem-sew-wag-wec:j:bh1,wag:j:min-max,koe-sch-wag:j:diff};
%
for the boolean hierarchy over arbitrary set rings, we refer to the early work
by Hausdorff~\cite{hau:b:sets}.  Note that $\DP = \bhlevel{2}$.

In his seminal paper~\cite{wag:j:min-max}, Wagner provided sufficient
conditions to prove problems complete for the levels of the boolean hierarchy.
In particular, he established the following lemma for $\bhlevel{2k}$.

\begin{lemma}
\label{lem:klaus}
{\bf \cite[Thm.~5.1(3)]{wag:j:min-max}} \quad Let $A$ be some $\np$-complete
problem, let $B$ be an arbitrary problem, and let $k \geq 1$ be fixed.  

If there exists a polynomial-time computable function $f$ such that, for all
strings $x_1, x_2, \ldots, x_{2k} \in \sigmastar$ satisfying $(\forall j\,:\,
1 \leq j < 2k)\, [x_{j+1} \in A \Lora x_{j} \in A]$, it holds that
\begin{eqnarray}
\label{eq:klaus-codp}
\|\{i \condition x_i \in A\}\| \mbox{ is odd}
 & \Longleftrightarrow & f(x_1, x_2, \ldots, x_{2k}) \in B,
\end{eqnarray}
then $B$ is $\bhlevel{2k}$-hard.
\end{lemma}

For fixed $k \geq 1$, let $M_k = \{6k+1, 6k+3, \ldots, 8k-1 \}$, and define
the problem $\exactcolor{M_k} = \{ G \condition \chi(G) \in M_k \}$.  In
particular, Wagner applied Lemma~\ref{lem:klaus} to prove that, for each $k
\geq 1$, $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete. For the special case
of $k = 1$, it follows that $\exactcolor{\{7\}}$ is DP-complete.

Wagner~\cite[p.~70]{wag:j:min-max} raised the question of how small the
numbers in a $k$-element set $M_k$ can be chosen such that $\exactcolor{M_k}$
still is $\bhlevel{2k}$-complete.  Consider the special case of $k = 1$.  It
is easy to see that $\exactcolor{\{3\}}$ is in NP and, thus, cannot be
DP-complete unless the boolean hierarchy collapses; see
Proposition~\ref{prop:exact-color} below.  Consequently, for $k = 1$, Wagner's
result leaves a gap in determining the precise threshold $t \in \{4, 5, 6,
7\}$ for which the problem $\exactcolor{\{t\}}$ jumps from NP to
DP-completeness.  Closing this gap, we show that it is DP-complete to
determine whether $\chi(G) = 4$.  More generally, answering Wagner's question
for each $k \geq 1$, we show that $\exactcolor{M_k}$ is
$\bhlevel{2k}$-complete for $M_k = \{3k+1, 3k+3, \ldots, 5k-1 \}$.

\section{Solving Wagner's Question}

\begin{proposition}
\label{prop:exact-color}
Fix any $k \geq 1$, and let $M_k$ be any set that contains $k$ noncontiguous
positive integers including~$3$.  Then, $\exactcolor{M_k}$ is in
$\bhlevel{2k-1}$; in particular, for $k = 1$, $\exactcolor{\{3\}}$ is
in~$\np$.  

Hence, $\exactcolor{M_k}$ is not $\bhlevel{2k}$-complete unless the boolean
hierarchy, and consequently the polynomial hierarchy, collapses.
\end{proposition}

\begin{proof}
  Fix any $k \geq 1$, and let $M_k$ be given as above.  
%
%
  Note that
\[
\exactcolor{M_k} = \bigcup_{i \in M_k} \exactcolor{\{i\}}.
\]
Since for each $i \in M_k$, $\exactcolor{\{i\}} = \{ G \condition \chi(G) \leq
i\} \cap \{ G \condition \chi(G) > i-1\}$ and since the set $\{ G \condition
\chi(G) \leq i\}$ is in~$\np$ and the set $\{ G \condition \chi(G) > i-1\}$ is
in~$\conp$, each of the $k-1$ sets $\exactcolor{\{i\}}$ with $i \in M_k -
\{3\}$ is in~$\DP$.  However, $\exactcolor{\{3\}}$ is even contained in~NP,
since it can be checked in polynomial time whether a given graph is
2-colorable, so $\{ G \condition \chi(G) > 2\}$ is in~$\p$.  It follows that
$\exactcolor{M_k}$ is in $\bhlevel{2k-1}$.~\qed
\end{proof}

\begin{theorem}
  For fixed $k \geq 1$, let $M_k = \{3k+1, 3k+3, \ldots, 5k-1 \}$.  Then,
  $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete.  In particular, for $k = 1$,
  it follows that $\exactcolor{\{4\}}$ is $\DP$-complete.
\end{theorem}

\begin{proof}
  We apply Lemma~\ref{lem:klaus} with $A$ being the NP-complete problem
  $\threesat$ and $B$ being the problem $\exactcolor{M_k}$, where $M_k =
  \{3k+1, 3k+3, \ldots, 5k-1 \}$ for fixed~$k$.  The standard reduction
  $\sigma$ from $\threesat$ to $\threecolor$ has the following
  property~\cite{gar-joh:b:int}:
\begin{eqnarray}
\label{eq:three-four-color}
\phi \in \threesat \Lora \chi(\sigma(\phi)) = 3 & \mbox{ and } & 
\phi \not\in \threesat \Lora \chi(\sigma(\phi)) = 4.
\end{eqnarray}

Using the PCP theorem, Khanna, Linial, and
Safra~\cite{kha-lin-saf:j:fourcoloring-threecolorable-graphs} showed that it
is NP-hard to color a 3-colorable graph with only four colors.  Guruswami and
Khanna~\cite{gur-kha:c:fourcoloring-threecolorable-graphs} gave a novel proof
of the same result that does not rely on the PCP theorem.  We use their direct
transformation, call it~$\rho$, that consists of two subsequent
reductions---first from $\threesat$ to the independent set problem, and then
from the independent set problem to $\threecolor$---such that $\phi \in
\threesat$ implies $\chi(\rho(\phi)) = 3$, and $\phi \not\in \threesat$
implies $\chi(\rho(\phi)) \geq 5$.  Guruswami and
Khanna~\cite{gur-kha:c:fourcoloring-threecolorable-graphs} note that the graph
$H = \rho(\phi)$ they construct always is 6-colorable.  In fact, their
construction even gives that $H$ always is 5-colorable; hence, we have:
\begin{eqnarray}
\label{eq:three-five-color}
\phi \in \threesat \Lora \chi(\rho(\phi)) = 3 & \mbox{ and } & 
\phi \not\in \threesat \Lora \chi(\rho(\phi)) = 5.
\end{eqnarray}
To see why, look at the reduction
in~\cite{gur-kha:c:fourcoloring-threecolorable-graphs}.  The graph $H$
consists of tree-like structures whose vertices are replaced by $3 \times 3$
grids, which always can be colored with three colors, say~1, 2, and~3.  In
addition, some leafs of the tree-like structures are connected by leaf-level
gadgets of two types, the ``same row kind'' and the ``different row
kind.''~~The latter gadgets consist of two vertices connected to some grids,
and thus can always be colored with two additional colors.  The leaf-level
gadgets of the ``same row kind'' consist of a triangle whose vertices are
adjacent to two grid vertices each.  Hence, regardless of which 3-coloring is
used for the grids, one can always color one triangle vertex, say~$t_1$, with
a color $c \in \{1, 2, 3\}$ such that $c$ is different from the colors of the
two grid vertices adjacent to~$t_1$.  Using two additional colors for the
other two triangle vertices implies $\chi(H) \leq 5$, which proves
Equation~(\ref{eq:three-five-color}).

The join operation $\oplus$ on graphs is defined as follows: Given two
disjoint graphs $A = (V_A, E_A)$ and~$B = (V_B, E_B)$, their join $A \oplus B$
is the graph with vertex set $V_{A \oplus B} = V_A \cup V_B$ and edge set
$E_{A \oplus B} = E_A \cup E_B \cup \{ \{a, b\} \condition a \in V_A \mbox{
  and } b \in V_B\}$.  Note that $\oplus$ is an associative operation on
graphs and $\chi(A \oplus B) = \chi(A) + \chi(B)$.

Let $\phi_{1}, \phi_{2}, \ldots , \phi_{2k}$ be $2k$ given boolean formulas
satisfying $\phi_{j+1} \in \threesat \Lora \phi_{j} \in \threesat$ for each
$j$ with $1 \leq j < 2k$.  Define $2k$ graphs $H_{1}, H_{2}, \ldots , H_{2k}$
as follows.  For each $i$ with $1 \leq i \leq k$, define $H_{2i-1} =
\rho(\phi_{2i-1})$ and $H_{2i} = \sigma(\phi_{2i})$.  By
Equations~(\ref{eq:three-four-color}) and~(\ref{eq:three-five-color}),
\begin{eqnarray}
\label{eq:three-four-five}
\chi(H_j) & = & \left\{
\begin{array}{ll}
3 & \mbox{if $1 \leq j \leq 2k$ and $\phi_j \in \threesat$} \\
4 & \mbox{if $j = 2i$ for some $i \in \{1, 2, \ldots , k\}$ and $\phi_j
  \not\in \threesat$} \\
5 & \mbox{if $j = 2i - 1$ for some $i \in \{1, 2, \ldots , k\}$ and $\phi_j
  \not\in \threesat$.}
\end{array}
\right.
\end{eqnarray}
For each $i$ with $1 \leq i \leq k$, define the graph $G_i$ to be the disjoint
union of the graphs $H_{2i - 1}$ and~$H_{2i}$.  Thus, $\chi(G_i) =
\max\{\chi(H_{2i - 1}),\, \chi(H_{2i})\}$, for each $i$ with $1 \leq i \leq
k$.  The construction of our reduction $f$ is completed by defining
$f(\phi_{1}, \phi_{2}, \ldots , \phi_{2k}) = G$, where the graph $G =
\bigoplus_{i = 1}^{k} G_i$ is the join of the graphs $G_1, G_2, \ldots , G_k$.
Thus, 
\begin{equation}
\label{eq:sum-joins}
\chi(G) = \sum_{i = 1}^{k} \chi(G_i)
 = \sum_{i = 1}^{k} \max\{\chi(H_{2i - 1}),\, \chi(H_{2i})\}.  
\end{equation}
It follows from our construction that
\begin{eqnarray*}
\lefteqn{\|\{i \condition \phi_i \in \threesat\}\| \mbox{ is odd} } \\
 & \Longleftrightarrow & (\exists i \,:\, 1 \leq i \leq k)\, 
[\phi_{1}, \ldots , \phi_{2i - 1} \in \threesat \mbox{ and }
\phi_{2i}, \ldots , \phi_{2k} \not\in \threesat ] \\
%
%
%
%
 & \stackrel{(\ref{eq:three-four-five}),\, (\ref{eq:sum-joins})}
            {\Longleftrightarrow} & 
(\exists i \,:\, 1 \leq i \leq k)\, 
\left[\sum_{j = 1}^{k} \chi(G_j) = 3(i - 1) + 4 + 5(k - i)
                                 = 5k - 2i + 1 \right] \\
 & \stackrel{(\ref{eq:sum-joins})}
            {\Longleftrightarrow} & 
\chi(G) \in M_k = \{3k+1, 3k+3, \ldots, 5k-1 \} \\
 & \Longleftrightarrow & 
f(\phi_{1}, \phi_{2}, \ldots , \phi_{2k}) = G \in \exactcolor{M_k}.
\end{eqnarray*}

Hence, Equation~(\ref{eq:klaus-codp}) is satisfied.  By Lemma~\ref{lem:klaus},
$\exactcolor{M_k}$ is $\bhlevel{2k}$-complete.~\qed
\end{proof}

\bigskip

{\samepage
\noindent 
{\bf Acknowledgments.} \quad Interesting discussions with Klaus Wagner,
Venkatesan Guruswami, Edith and Lane Hemaspaandra, Dieter Kratsch, and Gerd
Wechsung are gratefully acknowledged.  }
%

{\small 

%
\bibliography{/sartre2/home2/rothe/BIGBIB/joergbib}

}

\end{document}


main.bbl
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{CGH{\etalchar{+}}89}

\bibitem[Bei91]{bei:j:bounded-queries}
R.~Beigel.
\newblock Bounded queries to {SAT} and the boolean hierarchy.
\newblock {\em Theoretical Computer Science}, 84(2):199--223, 1991.

\bibitem[CGH{\etalchar{+}}88]{cai-gun-har-hem-sew-wag-wec:j:bh1}
J.~Cai, T.~Gundermann, J.~Hartmanis, L.~Hemachandra, V.~Sewelson, K.~Wagner,
  and G.~Wechsung.
\newblock The boolean hier\-archy {I}: {S}truc\-tural proper\-ties.
\newblock {\em SIAM Jour\-nal on Com\-pu\-ting}, 17(6):1232--1252, 1988.

\bibitem[CGH{\etalchar{+}}89]{cai-gun-har-hem-sew-wag-wec:j:bh2}
J.~Cai, T.~Gundermann, J.~Hartmanis, L.~Hemachandra, V.~Sewelson, K.~Wagner,
  and G.~Wechsung.
\newblock The boolean hierarchy {II}: Applications.
\newblock {\em SIAM Journal on Computing}, 18(1):95--111, 1989.

\bibitem[Cha91]{cha:thesis}
R.~Chang.
\newblock {\em On the Structure of {NP} Computations under Boolean Operators}.
\newblock PhD thesis, Cornell University, Ithaca, NY, 1991.

\bibitem[CM87]{cai-mey:j:dp}
J.~Cai and G.~Meyer.
\newblock Graph minimal uncolorability is {$\rm D^P$}-complete.
\newblock {\em SIAM Journal on Computing}, 16(2):259--277, April 1987.

\bibitem[GJ79]{gar-joh:b:int}
M.~Garey and D.~Johnson.
\newblock {\em Computers and Intractability: A Guide to the Theory of
  NP-Completeness}.
\newblock {W. H. Freeman and Company}, New York, 1979.

\bibitem[GK00]{gur-kha:c:fourcoloring-threecolorable-graphs}
V.~Guruswami and S.~Khanna.
\newblock On the hardness of 4-coloring a 3-colorable graph.
\newblock In {\em Proceedings of the 15th Annual IEEE Conference on
  Computational Complexity}, pages 188--197. IEEE Computer Society Press, May
  2000.

\bibitem[Hau14]{hau:b:sets}
F.~Hausdorff.
\newblock {\em Grundz\"{u}ge der Mengenlehre}.
\newblock {Walter de Gruyten and Co.}, 1914.

\bibitem[HR97]{hem-rot:j:boolean}
L.~Hemaspaandra and J.~Rothe.
\newblock Unambiguous computation: {B}oolean hierarchies and sparse
  {T}uring-complete sets.
\newblock {\em SIAM Journal on Computing}, 26(3):634--653, 1997.

\bibitem[Kad88]{kad:joutdatedbychangkadin:bh}
J.~Kadin.
\newblock The polynomial time hierarchy collapses if the boolean hierarchy
  collapses.
\newblock {\em SIAM Journal on Computing}, 17(6):1263--1282, 1988.
\newblock Erratum appears in the same journal, 20(2):404.

\bibitem[KLS00]{kha-lin-saf:j:fourcoloring-threecolorable-graphs}
S.~Khanna, N.~Linial, and S.~Safra.
\newblock On the hardness of approximating the chromatic number.
\newblock {\em Combinatorica}, 20(3):393--415, 2000.

\bibitem[KSW87]{koe-sch-wag:j:diff}
J.~K{\"{o}}bler, U.~Sch\"{o}ning, and K.~Wagner.
\newblock The difference and truth-table hierarchies for {NP}.
\newblock {\em R.A.I.R.O. Informatique th\'{e}orique et Applications},
  21:419--435, 1987.

\bibitem[PY84]{pap-yan:j:dp}
C.~Papadimitriou and M.~Yannakakis.
\newblock The complexity of facets (and some facets of complexity).
\newblock {\em Journal of Computer and System Sciences}, 28(2):244--259, 1984.

\bibitem[Wag87]{wag:j:min-max}
K.~Wagner.
\newblock More complicated questions about maxima and minima, and some closures
  of {NP}.
\newblock {\em Theoretical Computer Science}, 51:53--80, 1987.

\bibitem[Wag90]{wag:j:bounded}
K.~Wagner.
\newblock Bounded query classes.
\newblock {\em SIAM Journal on Computing}, 19(5):833--846, 1990.

\end{thebibliography}
