New approximation guarantee for chromatic number

DOI10.1145/1132516.1132548MaRDI QIDQ2931386zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

semidefinite programmingapproximation algorithmschromatic numbergraph coloring

Mathematics Subject Classification ID

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

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

Cited in

(22)

• A new method of proving theorems on chromatic index
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• Hardness of rainbow coloring hypergraphs
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• scientific article; zbMATH DE number 6988815 (Why is no real title available?)
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• A better performance guarantee for approximate graph coloring
• scientific article; zbMATH DE number 7561683 (Why is no real title available?)
• Integrality gaps for colorful matchings
• On the tractability of coloring semirandom graphs
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• Linear index coding via semidefinite programming
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• New tools for graph coloring
• Approximating the orthogonality dimension of graphs and hypergraphs
• Robust Factorizations and Colorings of Tensor Graphs
• Matrix relaxations in combinatorial optimization
• Convex relaxations and integrality gaps
• Hypergraph list coloring and Euclidean Ramsey theory
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Inductive graph invariants and approximation algorithms
• New heuristics for the vertex coloring problem based on semidefinite programming

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)