Gap, cosum and product properties of the θ′ bound on the clique number

DOI10.1080/02331930903395634zbMath1214.05102MaRDI QIDQ3066919

Florian Frommlet, Immanuel M. Bomze, Marco Locatelli

Publication date: 20 January 2011

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331930903395634

zbMATH Keywords

semidefinite programming; copositive programming; circulant graph; maximum clique problem; graph product

Mathematics Subject Classification ID

90C22: Semidefinite programming

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C76: Graph operations (line graphs, products, etc.)

Related Items

A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations, A Sum of Squares Characterization of Perfect Graphs, Quadratic factorization heuristics for copositive programming, Factorization and cutting planes for completely positive matrices by copositive projection, Copositivity cuts for improving SDP bounds on the clique number

Cites Work

• Semidefinite programming relaxations for graph coloring and maximal clique problems
• New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Approximation of the Stability Number of a Graph via Copositive Programming
• A comparison of the Delsarte and Lovász bounds
• On the Shannon capacity of a graph
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Unnamed Item