Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization

DOI10.1137/070683520MaRDI QIDQ3629508zbMATH OpenOpenAlexFDO

Authors Nebojša Gvozdenović, Monique Laurent

Publication date 27 May 2009

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/070683520

zbMATH Keywords

semidefinite programmingchromatic numberKneser graphTerwilliger algebraHamming graphLovász theta number

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Semidefinite programming relaxations for graph coloring and maximal clique problems
• A lower bound for the chromatic number of a graph
• Approximate graph coloring by semidefinite programming
• The Operator \Psi for the Chromatic Number of a Graph
• New heuristics for the vertex coloring problem based on semidefinite programming

Cited in

(20)

• Exact solution of graph coloring problems via constraint programming and column generation
• Chromatic Gallai identities operating on Lovász number
• The sandwich line graph
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
• Symmetric sums of squares over \(k\)-subset hypercubes
• Partial Lasserre relaxation for sparse Max-Cut
• Matrix relaxations in combinatorial optimization
• On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
• New heuristics for the vertex coloring problem based on semidefinite programming
• Copositive programming motivated bounds on the stability and the chromatic numbers
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• A lower bound for the chromatic number of a graph
• Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
• The CP-matrix approximation problem
• scientific article; zbMATH DE number 5990470 (Why is no real title available?)
• Copositive programming
• scientific article; zbMATH DE number 2166870 (Why is no real title available?)
• Block-diagonal semidefinite programming hierarchies for 0/1 programming
• The Operator \Psi for the Chromatic Number of a Graph
• Invariant Semidefinite Programs

Describes a project that uses

Uses Software

• Max-AO

This page was built for publication: Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization

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