Exact Complexity of Exact-Four-Colorability

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,>...,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\ge 1$, we show that $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete for $M_k=\{3k+1,3k+3,...,5k-1\}$.

arXiv comment5 pages