Strengthening the Lovász 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
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

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.