# Razborov's Approximation methods

The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem.

People in parameterized complexity theory strongly believe that k-colooring is strictly harder than the k-clique problem, because k-clique problems can be solved by an exhaustive search of all ${n \choose k}$ potential cliques while k-coloring is NP-complete for a fixed k (k=3). k-coloring is also monotone function.

It seems to be natural that the approx method is appropriate for deriving lower bounds of the problem but I haven't seen a paper which justifies this intuition.

Is Razborov's method useful to derive the exponential monotone lower bound of k-coloring?

• k-coloring is not a monotone function, it cannot be computed by a monotone circuit. – Kaveh May 17 '12 at 20:17
• @Kaveh: k-coloring is monotone downward - if a graph has a k-coloring, then so does any subgraph. So non-k-colorability could be computed by a monotone circuit. – Joshua Grochow May 17 '12 at 20:19
• @Joshua, good point, we can also change the representation of the input, representing existence of edges by 0, I guess that would be an easier way to deal with the monotonicity issue. – Kaveh May 17 '12 at 20:25
• Hi, Kaveh and Grochow – Jeigh May 18 '12 at 1:18
• @Jeigh please take the time to proofread your posts and fix obvious spelling errors. (if you're using a browser like firefox, it will even indicate where the errors are). – Suresh Venkat May 18 '12 at 2:49

Let $f(G)=1$ iff $G$ is not $(k-1)$-colorable. Then $f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs, just like the $k$-clique function does. So, the lower bounds for clique hold also for $f$.
• Hi Jukna, is your statement that we can take $k$-cliques as "positive test inputs" and $(k-1)$-partite graphs as "negative inputs" and lower bound is the same value $2^{\varepsilon \sqrt{k}}$ of $k-clique$ lower bound ? – Jeigh May 18 '12 at 10:18