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

DOI10.1137/070683520zbMATH Open1213.05081OpenAlexW2094911282MaRDI QIDQ3629508FDOQ3629508

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

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

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)

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
• 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
• 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
• Title not available (Why is that?)
• Copositive programming
• Title not available (Why is that?)
• Block-diagonal semidefinite programming hierarchies for 0/1 programming
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Invariant Semidefinite Programs

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)