Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming

DOI10.1137/19M1306427zbMath1481.90247arXiv1910.05586OpenAlexW3216274422MaRDI QIDQ5013579

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

Publication date: 1 December 2021

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

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

zbMATH Keywords

theta functionstability numberchromatic numbergauge dualityHoffman bound

Mathematics Subject Classification ID

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

Cites Work

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