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

approximation algorithmschromatic numbergraph coloringsemidefinite programming

Mathematics Subject Classification ID

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

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

(24)

• 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
• 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
• New heuristics for the vertex coloring problem based on semidefinite programming
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• New approximation algorithms for graph coloring
• scientific article; zbMATH DE number 6988815 (Why is no real title available?)
• Approximating the orthogonality dimension of graphs and hypergraphs
• Inductive graph invariants and approximation algorithms
• Hardness of rainbow coloring hypergraphs
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Linear index coding via semidefinite programming
• Approximating the orthogonality dimension of graphs and hypergraphs
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Robust Factorizations and Colorings of Tensor Graphs
• Improved linearly ordered colorings of hypergraphs via SDP rounding
• A new method of proving theorems on chromatic index
• A better performance guarantee for approximate graph coloring
• On the tractability of coloring semirandom graphs

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)