Return to Question

edited tag

edited Jul 12 at 12:09

Gerry Myerson
15.7k●1●47●87

view source

asked Jul 12 at 7:47

unknown (google)
1,009●4●11

Grothendieck Constant of a graph and approximation limits

Let $K(G)$ be the Grothendieck constant of a graph with adjacency matrix $A$. How is $K(G)$ precisely related to approximation limits for some standard NP complete problems such as Chromatic, Independence and Clique number approximation?

graph theory