| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Sao Paulo, Dept Comp Sci, BR-05508090 Sao Paulo, SP - Brazil
[2] Univ Fed Minas Gerais, Dept Comp Sci, BR-31270901 Belo Horizonte, MG - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 35, n. 4, p. 2880-2907, 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
The notion of duality is a key element in understanding the interplay between the stability and chromatic numbers of a graph. This notion is a central aspect in the celebrated theory of perfect graphs and is further and deeply developed in the context of the Lovasz theta function and its equivalent characterizations and variants. The main achievement of this paper is the introduction of a new family of norms, providing upper bounds for the stability number, that are obtained through duality from the norms motivated by Hoffman's lower bound for the chromatic number, and which achieve the (complementary) Lovasz theta function at their optimum. As a consequence, our norms make it formal that Hoffman's bound for the chromatic number and the Delsarte-Hoffman ratio bound for the stability number are indeed dual. Further, we show that our new bounds strengthen the convex quadratic bounds for the stability number studied by Luz and Schrijver, and which achieve the Lovasz theta function at their optimum. One of the key observations regarding weighted versions of these bounds is that, for any upper bound for the stability number of a graph which is a positive definite monotone gauge function, its gauge dual is a lower bound on the fractional chromatic number, and conversely. Our presentation is elementary and accessible to a wide audience. (AU) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |