7
$\begingroup$

So I came up with a decision procedure for 3SAT which would seem to be completeable in a polynomial amount of time. Naturally, I am assuming it is incorrect, but I don't know where the mistake is.

Ok, so given an instance of 3SAT, reduce it to 3 colorability. A polynomial time method for doing this can be found here.

A necessary condition for 3 colorability is that it doesn't contain the complete graph on 4 vertices as a minor.

Hadwiger's conjecture implies that this is also sufficient for 3 colorability on loopless graphs, (maybe here is the problem; did I misunderstand something?) and it has apparently been proven for this case.

So in this case, our graph has one forbidden minor which stays constant over all 3SAT instances created in this manner. Testing if a minor is in a given graph is fixed parameter tractable (with a constant that depends superpolynomially on the minor) , and given that this parameter is fixed, our problem is solvable in a polynomially bounded amount of time.

$\endgroup$
1
  • 3
    $\begingroup$ +1 for trying to prove that NP=P and realizing that the proof is probably flawed :-) $\endgroup$
    – joriki
    Jan 23, 2012 at 9:17

1 Answer 1

8
$\begingroup$

There are 3-colorable graphs with $K_4$ as a minor.

For instance:

enter image description here

So your assumption about necessity is incorrect. The sufficiency is true (and not a conjecture).

(Also, there is really no need to bring 3SAT into the picture, 3-colorability (of loopless graphs) is 'classically' known to be NP-Hard).

For a graph with no $K_4$ (as subgraph) which requires $4$-colours:

enter image description here

$\endgroup$
8
  • 1
    $\begingroup$ Ok, seems like I conflated subgraph and minor. $\endgroup$ Jan 23, 2012 at 9:43
  • $\begingroup$ Just as a help, can you give an example of a graph that requires four colors that doesn't contain $K_4$? $\endgroup$ Jan 23, 2012 at 9:56
  • $\begingroup$ @Tim: If it does not contain $K_4$ as a minor, then it is 3-colorable (the sufficiency part). So that is not possible. $\endgroup$
    – Aryabhata
    Jan 23, 2012 at 10:05
  • $\begingroup$ No, sorry, I think you misunderstood my question, I wasn't asking about graphs that don't contain it as a minor. I was asking about graphs that don't contain it as an isomorphic copy. $\endgroup$ Jan 23, 2012 at 10:09
  • 1
    $\begingroup$ @TIm: I see. Apologies. See the edited answer for a figure. The idea was to replace one of the edges of $K_4$ with a gadget which behaves like an edge, when using only 3 colours. $\endgroup$
    – Aryabhata
    Jan 23, 2012 at 10:19

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.