Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring

DOI10.1007/s101070100246zbMath1059.05052OpenAlexW1998838742MaRDI QIDQ1774164

Philippe Meurdesoif

Publication date: 29 April 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s101070100246

zbMATH Keywords

SDP relaxationCombinatorial optimizationGraph coloringLovász \(\theta\)-number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items (7)

Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Semidefinite programming relaxations for graph coloring and maximal clique problems ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ Chromatic Gallai identities operating on Lovász number ⋮ A semidefinite programming-based heuristic for graph coloring ⋮ Unnamed Item ⋮ Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition

Uses Software

• SDPpack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zero knowledge and the chromatic number
• The sandwich theorem
• Explicit Ramsey graphs and orthonormal labelings
• Approximating the independence number via the \(\vartheta\)-function
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Matrix Analysis
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• On the Shannon capacity of a graph
• On the hardness of approximating minimization problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring