Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
type: Item
instance of: scholarly article
title: Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
zbMATH Open document ID: 1059.05052
author: Philippe Meurdesoif
published in: Mathematical Programming. Series A. Series B
publication date: 2005-04-29T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 2162522
zbMATH Keywords: Combinatorial optimization
zbMATH Keywords: SDP relaxation
zbMATH Keywords: Graph coloring
zbMATH Keywords: Lovász \(\theta\)-number
describes a project that uses: SDPpack
MaRDI profile type: Publication
full work available at URL: s101070100246
OpenAlex ID: W1998838742
cites work: Explicit Ramsey graphs and orthonormal labelings
cites work: Approximating the independence number via the \(\vartheta\)-function
cites work: Zero knowledge and the chromatic number
cites work: Q3499508
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Matrix Analysis
cites work: Approximate graph coloring by semidefinite programming
cites work: The sandwich theorem
cites work: SDP relaxations in combinatorial optimization from a Lagrangian viewpoint.
cites work: On the Shannon capacity of a graph
cites work: On the hardness of approximating minimization problems
cites work: Q4194987
cites work: A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
cites work: A comparison of the Delsarte and Lovász bounds
DOI: 10.1007/S101070100246
Recommended article: Improved bounds on coloring of graphs
Recommended article: A bound on the strong chromatic index of a graph
Recommended article: On strict strong coloring of graphs
Recommended article: Approximations for -Colorings of Graphs
Recommended article: \(b\)-coloring of tight bipartite graphs and the Erdős-Faber-Lovász conjecture
Recommended article: An improved bound for the strong chromatic number
Recommended article: Improved hardness for H-colourings of G-colourable graphs
Recommended article: \(d\)-strong total colorings of graphs
Recommended article: A new upper bound for total colourings of graphs
Recommended article: Q4952595
description: scientific article; zbMATH DE number 2162522