Randomized graph products chromatic numbers and the Lov'asz #-function
| Author(s) : | Uriel Feige, |
| Publisher : | N/A |
| Publication Date : | 1995 |
| ISSN : | N/A |
| Abstract : | For a graph G, let ff(G) denote the size of the largest independent set in G, and let #(G) denote the Lov'asz #-function on G. We prove that for some c? 0, there exists an infinite family of graphs such that #(G) ? ff(G)n=2 c, |