Strengthening the Lov¨¢sz htmlnonpaginated&src=55CR58U5U3XB6P68_html\MediaObjects/s101070100246flb1.gif"" border=""0"" /> bound for graph coloring

详细信息    查看全文

• 作者：Philippe Meurdesoif
• 关键词：Combinatorial optimization ; SDP relaxation ; Graph coloring ; Lov&aacute ; sz number
• 刊名：Mathematical Programming
• 出版年：2005
• 出版时间：January 2005
• 年：2005
• 卷：102
• 期：3
• 页码：577-588
• 全文大小：299 KB

文摘

The Lovász -number is a way to approximate the independence number of a graph, but also its chromatic number. We express the Lovász bound as the continuous relaxation of a discrete Lovász -number which we derive from Karger et al.s formulation, and which is equal to the chromatic number. We also give another relaxation à la Schrijver-McEliece, which is better than the Lovász -number.