Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming

DOI10.1137/19M1306427zbMATH Open1481.90247arXiv1910.05586OpenAlexW3216274422MaRDI QIDQ5013579FDOQ5013579

Authors: Nathan Benedetto Proença, Gabriel Coutinho, Marcel Kenji De Carli Silva 

Publication date: 1 December 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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 Lov'asz 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 from duality from the norms motivated by Hoffman's lower bound for the chromatic number and which achieve the (complementary) Lov'asz 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 Lov'asz 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.

Full work available at URL: https://arxiv.org/abs/1910.05586

Recommendations

• Copositive programming motivated bounds on the stability and the chromatic numbers
• A lower bound for the chromatic number of a graph
• More tales of Hoffman: bounds for the vector chromatic number of a graph
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• Bounds on the stability number of a graph via the inverse theta function

zbMATH Keywords

chromatic numbertheta functionstability numbergauge dualityHoffman bound

Mathematics Subject Classification ID

Quadratic programming (90C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Semidefinite programming (90C22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized inverses. Theory and applications.
• Title not available (Why is that?)
• Conic formulations of graph homomorphisms
• On the Shannon capacity of a graph
• Title not available (Why is that?)
• Infinite dimensional analysis. A hitchhiker's guide.
• Eigenvalue bounds for independent sets
• Geometric algorithms and combinatorial optimization.
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Title not available (Why is that?)
• Blocking and anti-blocking pairs of polyhedra
• The sandwich theorem
• A comparison of the Delsarte and Lovász bounds
• Title not available (Why is that?)
• Gauge optimization and duality
• Title not available (Why is that?)
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• An upper bound on the independence number of a graph computable in polynomial-time
• A Convex Quadratic Characterization of the Lovász Theta Number
• Title not available (Why is that?)
• Relaxations of vertex packing
• Anti-blocking polyhedra
• An axiomatic duality framework for the theta body and related convex corners
• An inertial lower bound for the chromatic number of a graph
• A quadratic programming approach to the determination of an upper bound on the weighted stability number
• Foundations of gauge and perspective duality
• A characterization of the weighted Lovász number based on convex quadratic programming

Cited In (1)

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

This page was built for publication: Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013579)