A new property of the Lovász number and duality relations between graph parameters

详细信息    查看全文

• 作者：Antonio Ací ; n^a ; ^b ; Runyao Duan^c ; ^d ; David E. Roberson^e ; Ana Belé ; n Sainz^b ; ^f ; Andreas Winter^a ; ^g ; ^{andreas.winter@uab.cat}
• 关键词：Graph ; Lov&aacute ; sz number ; Independence number ; Chromatic number ; Fractional packing number
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P3
• 页码：489-501
• 全文大小：499 K
• 卷排序：216

文摘

We show that for any graph GG, by considering “activation” through the strong product with another graph HH, the relation α(G)≤ϑ(G)α(G)≤ϑ(G) between the independence number and the Lovász number of GG can be made arbitrarily tight: Precisely, the inequality α(G⊠H)⩽ϑ(G⊠H)=ϑ(G)ϑ(H) becomes asymptotically an equality for a suitable sequence of ancillary graphs HH.This motivates us to look for other products of graph parameters of GG and HH on the right hand side of the above relation. For instance, a result of Rosenfeld and Hales states that α(G⊠H)⩽α∗(G)α(H), with the fractional packing number α∗(G)α∗(G), and for every GG there exists HH that makes the above an equality; conversely, for every graph HH there is a GG that attains equality.These findings constitute some sort of duality of graph parameters, mediated through the independence number, under which αα and α∗α∗ are dual to each other, and the Lovász number ϑϑ is self-dual. We also show duality of Schrijver’s and Szegedy’s variants ϑ−ϑ− and ϑ+ϑ+ of the Lovász number, and explore analogous notions for the chromatic number under strong and disjunctive graph products.