New approximation guarantee for chromatic number
DOI10.1145/1132516.1132548zbMATH Open1301.05324OpenAlexW2043963325MaRDI QIDQ2931386FDOQ2931386
Authors: Eden Chlamtac, Sanjeev Arora 
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
Recommendations
- New bounds for the chromatic number of graphs
- scientific article; zbMATH DE number 6988815
- New upper bounds for the chromatic number of a graph
- Improved hardness of approximating chromatic number
- New estimates for the gap chromatic number
- Approximating the chromatic polynomial
- A new bound on the cyclic chromatic number
- A new upper bound for the chromatic number of a graph
- New results on chromatic polynomials
- An approximation chromatic number of a graph
Graph algorithms (graph-theoretic aspects) (05C85) Semidefinite programming (90C22) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cited In (23)
- Convex Relaxations and Integrality Gaps
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- Title not available (Why is that?)
- New tools for graph coloring
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- A new method of proving theorems on chromatic index
- Hypergraph list coloring and Euclidean Ramsey theory
- On the tractability of coloring semirandom graphs
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- Matrix relaxations in combinatorial optimization
- New heuristics for the vertex coloring problem based on semidefinite programming
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Hardness of Rainbow Coloring Hypergraphs
- Title not available (Why is that?)
- Inductive graph invariants and approximation algorithms
- Robust Factorizations and Colorings of Tensor Graphs
- Title not available (Why is that?)
- A better performance guarantee for approximate graph coloring
- Title not available (Why is that?)
- Integrality gaps for colorful matchings
- Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
- Title not available (Why is that?)
This page was built for publication: New approximation guarantee for chromatic number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931386)
