Improved Hardness of Approximating Chromatic Number
From MaRDI portal
Publication:2851860
DOI10.1007/978-3-642-40328-6_17zbMath1407.68195arXiv1301.5216OpenAlexW1492972816MaRDI QIDQ2851860
Publication date: 4 October 2013
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1301.5216
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (8)
Topology and Adjunction in Promise Constraint Satisfaction ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ 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 ⋮ On percolation and ‐hardness ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Improved Hardness of Approximating Chromatic Number
