English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The notion of duality is a key element in understanding the interplay betweenthe stability and chromatic numbers of a graph. This notion is a central aspectin the celebrated theory of perfect graphs, and is further and deeply developedin the context of the Lov\'asz theta function and its equivalentcharacterizations and variants. The main achievement of this paper is theintroduction of a new family of norms, providing upper bounds for the stabilitynumber, that are obtained from duality from the norms motivated by Hoffman'slower bound for the chromatic number and which achieve the (complementary)Lov\'asz theta function at their optimum. As a consequence, our norms make itformal that Hoffman's bound for the chromatic number and the Delsarte-Hoffmanratio bound for the stability number are indeed dual. Further, we show that ournew bounds strengthen the convex quadratic bounds for the stability numberstudied by Luz and Schrijver, and which achieve the Lov\'asz theta function attheir optimum. One of the key observations regarding weighted versions of thesebounds is that, for any upper bound for the stability number of a graph whichis a positive definite monotone gauge function, its gauge dual is a lower boundon the fractional chromatic number, and conversely. Our presentation iselementary and accessible to a wide audience.

Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on SDP