<p>Let $f(G)=1$ iff $G$ is <strong>not</strong> $(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$.</p>

CC BY-SA 3.0
2012-05-18T10:18:50.273Z
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
CC BY-SA 3.0
2012-05-18T10:36:19.713Z
@Jeigh: Yes, exactly as you said. (B.t.w. I wrongly duplicated the answer as a comment. I would like to remove one of them. Do somebody knows how to delete things?)
Stasys
CC BY-SA 3.0
2012-05-18T11:35:54.207Z
Junkna, Thank you for your response. It seems that approximation methods can NOT capture the differences between k-clique problems and k-coloring problem in a parameterized complexity theoretic view which is stated in this question. Do you have any opinion or opposition about this my rough intuition?
Jeigh
CC BY-SA 3.0
2012-05-18T13:46:02.993Z
@Jeigh: No, we only know that lower bounds for k-Clique hold also for k-Coloring. But it may well be that the latter problem has another, more subtle positive and negative test inputs that are harder to separate (than those for Clique). Hence, it can well be that already 3-Coloring requires more than n^3 gates.
Stasys
CC BY-SA 3.0
2012-05-18T09:44:59.967Z
2017-08-22T17:15:40.520Z
2017-08-22T17:15:40.520Z
Stasys
<p>The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem. </p>

<p>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. </p>

<p>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. </p>

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

CC BY-SA 3.0
2012-05-17T20:17:07.537Z
k-coloring is not a monotone function, it cannot be computed by a monotone circuit.
Kaveh
CC BY-SA 3.0
2012-05-17T20:19:08.893Z
@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
CC BY-SA 3.0
2012-05-17T20:25:01.350Z
@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
CC BY-SA 3.0
2012-05-18T01:18:11.377Z
Hi, Kaveh and Grochow
Jeigh
CC BY-SA 3.0
2012-05-18T02:49:57.603Z
@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
<cc.complexity-theory><circuit-complexity><lower-bounds><graph-colouring>
Razborov's Approximation methods
Jeigh
# Razborov's Approximation methods

(Asked by: username_0 on 2012-05-17)

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?

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, graph-colouring

> **Comments:**
> **username_1**: k-coloring is not a monotone function, it cannot be computed by a monotone circuit.  
> **username_2**: @username_1: 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.  
> **username_1**: @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.  
> **username_0**: Hi, username_1 and Grochow  
> **username_3**: @username_0 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).  

---

## 1 answers

### Answer by username_4 on 2012-05-18. Score: 8 | Accepted answer

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$.

> **Comments:**
> **username_0**: 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 ?  
> **username_4**: @username_0: Yes, exactly as you said. (B.t.w. I wrongly duplicated the answer as a comment. I would like to remove one of them. Do somebody knows how to delete things?)  
> **username_0**: Junkna, Thank you for your response. It seems that approximation methods can NOT capture the differences between k-clique problems and k-coloring problem in a parameterized complexity theoretic view which is stated in this question. Do you have any opinion or opposition about this my rough intuition?  
> **username_4**: @username_0: No, we only know that lower bounds for k-Clique hold also for k-Coloring. But it may well be that the latter problem has another, more subtle positive and negative test inputs that are harder to separate (than those for Clique). Hence, it can well be that already 3-Coloring requires more than n^3 gates.  

---

