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

DOI10.1137/070683520zbMath1213.05081OpenAlexW2094911282MaRDI QIDQ3629508

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

Terwilliger algebraHamming graphsemidefinite programmingchromatic numberKneser graphLovász theta number

Mathematics Subject Classification ID

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

Related Items (16)

Matrix Relaxations in Combinatorial Optimization ⋮ Copositive programming motivated bounds on the stability and the chromatic numbers ⋮ Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ New heuristics for the vertex coloring problem based on semidefinite programming ⋮ On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs ⋮ Partial Lasserre relaxation for sparse Max-Cut ⋮ Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization ⋮ Symmetric sums of squares over \(k\)-subset hypercubes ⋮ Chromatic Gallai identities operating on Lovász number ⋮ Unnamed Item ⋮ The CP-Matrix Approximation Problem ⋮ Block-diagonal semidefinite programming hierarchies for 0/1 programming ⋮ Copositive Programming ⋮ Invariant Semidefinite Programs ⋮ Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

Uses Software

• Max-AO

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