Strengthening the Lovasz θ (G) bound for graph coloring
成果类型：
Article
署名作者：
Meurdesoif, P
署名单位：
Universite de Bordeaux
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s101070100246
发表日期：
2005
页码：
577-588
关键词：
摘要：
The Lovasz theta-number is a way to approximate the independence number of a graph, but also its chromatic number. We express the Lovasz bound as the continuous relaxation of a discrete Lovdsz theta-number which we derive from Karger et al.'s formulation, and which is equal to the chromatic number. We also give another relaxation a la Schrijver-McEliece, which is better than the Lovasz theta-number.