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?