TY - JOUR

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

AU - Acín, Antonio

AU - Duan, Runyao

AU - Roberson, David E.

AU - Sainz, Ana Belén

AU - Winter, Andreas

PY - 2017/1/10

Y1 - 2017/1/10

N2 - © 2016 Elsevier B.V. We show that for any graph G, by considering “activation” through the strong product with another graph H, the relation α(G)≤ϑ(G) between the independence number and the Lovász number of G 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 H. This motivates us to look for other products of graph parameters of G and H 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), and for every G there exists H that makes the above an equality; conversely, for every graph H there is a G 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.

AB - © 2016 Elsevier B.V. We show that for any graph G, by considering “activation” through the strong product with another graph H, the relation α(G)≤ϑ(G) between the independence number and the Lovász number of G 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 H. This motivates us to look for other products of graph parameters of G and H 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), and for every G there exists H that makes the above an equality; conversely, for every graph H there is a G 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.

KW - Chromatic number

KW - Fractional packing number

KW - Graph

KW - Independence number

KW - Lovász number

U2 - 10.1016/j.dam.2016.04.028

DO - 10.1016/j.dam.2016.04.028

M3 - Article

VL - 216

SP - 489

EP - 501

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -