Chromatic Gallai identities operating on Lovasz number

• 成果类型: Article
• 署名作者: Cornaz, Denis; Meurdesoif, Philippe
• 署名单位: Universite PSL; Universite Paris-Dauphine; Universite de Bordeaux
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0636-1
• 发表日期: 2014
• 页码: 347-368
• 关键词: graph; bounds; gap

摘要

If is a triangle-free graph, then two Gallai identities can be written as , where and denote the stability number and the clique-partition number, and is the line graph of . We show that, surprisingly, both equalities can be preserved for any graph by deleting the edges of the line graph corresponding to simplicial pairs of adjacent arcs, according to any acyclic orientation of . As a consequence, one obtains an operator which associates to any graph parameter such that for all graph , a graph parameter such that for all graph . We prove that and that for all graph , where is Lovasz theta function and is the fractional clique-partition number. Moreover, for triangle-free . Comparing to the previous strengthenings and of , numerical experiments show that is a significant better lower bound for than .