1
$\begingroup$

(Disclaimer: I suspect the answer is no, but I fail to see why)

Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture:

ph

The point is that if in a given graph $G$ some-one gives you four connected subgraphs $G_1$, $G_2$, $G_3$, $G_4$ (here illustrated with grey boxes) such that for each of the six combinations $(i, j)$ there is at least one edge in $G$ connecting a vertex in $G_i$ to one in $G_j$, then the conjecture claims that there is no 3-coloring of the big graph $G$.

Suppose that Hadwiger's conjecture is true. Wouldn't this put 3-coloring in coNP? At least to me it seems that once someone gives you $G_1, G_2, G_3, G_4$ their connectedness and existence of 6 edges connecting the four subgraphs can be checked in time quadratic in the number of vertices of the big graph $G$.

But if indeed 3-coloring is in coNP, wouldn't that put all of NP in coNP thus making these complexity classes equal?

This seems wrong, my impression was that both Hadwiger's conjecture and $NP \neq coNP$ are widely believed, so most likely something is wrong with my reasoning above.

But what?

$\endgroup$
12
$\begingroup$

I think the problem here is that you are stating the converse of Hadwiger's conjecture. The conjecture (according to Wikipedia) states that "if a graph needs at least k colors for a proper coloring, then it contains a $K_k$ minor (i.e. there exist subgraphs $G_1,\ldots,G_k$ as you state)". You are talking about the assertion that "If a graph has a $K_k$ minor, then it needs at least k colors for a proper coloring".

These two are not equivalent. Indeed, the latter statement is false. Consider for example a $K_{n,n}$. This graph contains a $K_n$ minor (take a perfect matching, this gives a collection of $n$ connected components all of which have edges to each other). However, its chromatic number is 2.

$\endgroup$
  • $\begingroup$ Yes that's it, thank you! $\endgroup$ – Vincent Apr 3 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.