New approximation guarantee for chromatic number

DOI10.1145/1132516.1132548zbMath1301.05324MaRDI 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 programming; graph coloring; chromatic number; approximation algorithms

Mathematics Subject Classification ID

90C22: Semidefinite programming

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Unnamed Item, Inductive graph invariants and approximation algorithms, Hardness of Rainbow Coloring Hypergraphs, Finding Pseudorandom Colorings of Pseudorandom Graphs, Unnamed Item, Unnamed Item, Unnamed Item, New heuristics for the vertex coloring problem based on semidefinite programming, Symmetry breaking depending on the chromatic number or the neighborhood growth, On the tractability of coloring semirandom graphs, Integrality gaps for colorful matchings, Convex Relaxations and Integrality Gaps, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, Matrix Relaxations in Combinatorial Optimization, 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, New Tools for Graph Coloring, Hypergraph list coloring and Euclidean Ramsey theory, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies