New approximation guarantee for chromatic number

DOI10.1145/1132516.1132548zbMath1301.05324OpenAlexW2043963325MaRDI QIDQ2931386

Sanjeev Arora, Eden Chlamtáč

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132548

zbMATH Keywords

semidefinite programminggraph coloringchromatic numberapproximation algorithms

Mathematics Subject Classification ID

Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (20)

Matrix Relaxations in Combinatorial Optimization ⋮ New heuristics for the vertex coloring problem based on semidefinite programming ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Inductive graph invariants and approximation algorithms ⋮ Integrality gaps for colorful matchings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ On the tractability of coloring semirandom graphs ⋮ Unnamed Item ⋮ Convex Relaxations and Integrality Gaps ⋮ New Tools for Graph Coloring ⋮ Hypergraph list coloring and Euclidean Ramsey theory ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Unnamed Item ⋮ Hardness of Rainbow Coloring Hypergraphs ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs

This page was built for publication: New approximation guarantee for chromatic number