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

DOI10.1080/02331930903395634MaRDI QIDQ3066919zbMATH OpenOpenAlexFDO

Authors Immanuel M. Bomze, Florian Frommlet, 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

circulant graphcopositive programminggraph productmaximum clique problemsemidefinite programming

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76) Semidefinite programming (90C22)

Recommendations

• Copositivity cuts for improving SDP bounds on the clique number
• A comparison of the Delsarte and Lovász bounds
• Clique, chromatic, and Lovász numbers of certain circulant graphs
• scientific article; zbMATH DE number 1507223
• scientific article; zbMATH DE number 4199650

Cites work

• A comparison of the Delsarte and Lovász bounds
• Approximation of the stability number of a graph via copositive programming
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• scientific article; zbMATH DE number 1384868 (Why is no real title available?)
• New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
• On the Shannon capacity of a graph
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Semidefinite programming relaxations for graph coloring and maximal clique problems

Cited in

(5)

• Factorization and cutting planes for completely positive matrices by copositive projection
• Copositivity cuts for improving SDP bounds on the clique number
• A notion of total dual integrality for convex, semidefinite, and extended formulations
• Quadratic factorization heuristics for copositive programming
• A Sum of Squares Characterization of Perfect Graphs

This page was built for publication: Gap, cosum and product properties of the \(\theta ^{\prime}\) bound on the clique number

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