New approximation guarantee for chromatic number
From MaRDI portal
Publication:2931386
DOI10.1145/1132516.1132548zbMath1301.05324MaRDI QIDQ2931386
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
90C22: Semidefinite programming
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
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, 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