Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
From MaRDI portal
Publication:3629508
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
Terwilliger algebraHamming graphsemidefinite programmingchromatic numberKneser graphLovász theta number
Semidefinite programming (90C22) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)
Related Items
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
