Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VECTOR CHROMATIC NUMBER:
Reports tagged with vector chromatic number:
TR03-073 | 11th June 2003
Amin Coja-Oghlan

The Lovasz number of random graph

We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$
of the independence number and the corresponding relaxations of the
chromatic number on random graphs G(n,p). We prove that \theta is
concentrated about its mean, and that the relaxations of the chromatic
number in the case ... more >>>




ISSN 1433-8092 | Imprint