Journal article
Randomized graph products, chromatic numbers, and the Lovasz theta-function
Combinatorica, Vol.17(1), pp.79-90
1997
Abstract
For a graph G, let alpha(G) denote the size of the largest independent set in G, and let theta(G) denote the Lovasz theta-function on G. We prove that for some c > 0, there exists an infinite family of graphs such that theta(G) > alpha(G)n/2(c root log n), where n denotes the number of vertices in a graph. This disproves a known conjecture regarding the theta function. As part of our proof, we analyse the behavior of the chromatic number in graphs under a randomized version of graph products. This analysis extends earlier work of Linial and Vazirani, and of Berman and Schnitger, and may be of independent interest.
Details
- Title
- Randomized graph products, chromatic numbers, and the Lovasz theta-function
- Creators
- Uriel Feige (null) - 972WIS_INST___83
- Resource Type
- Journal article
- Publication Details
- Combinatorica, Vol.17(1), pp.79-90; 1997
- Number of pages
- 12
- Language
- English
- DOI
- https://doi.org/10.1007/BF01196133
- Record Identifier
- 993267884303596
Metrics
10 Record Views