On the hardness of approximating the chromatic number
From MaRDI portal
Publication:5932643
DOI10.1007/s004930070013zbMath0964.68065OpenAlexW2104254886MaRDI QIDQ5932643
Nathan Linial, Sanjeev Khanna, Shmuel Safra
Publication date: 12 June 2001
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930070013
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (27)
Towards optimal lower bounds for clique and chromatic number. ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Tensors in computations ⋮ Matrix Relaxations in Combinatorial Optimization ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Unnamed Item ⋮ 5-list coloring toroidal 6-regular triangulations in linear time ⋮ 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 ⋮ Linear Index Coding via Semidefinite Programming ⋮ Balanced coloring of bipartite graphs ⋮ Unnamed Item ⋮ Exact complexity of exact-four-colorability ⋮ Notes on tree- and path-chromatic number ⋮ Hypergraph list coloring and Euclidean Ramsey theory ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Unnamed Item ⋮ Graph coloring by multiagent fusion search ⋮ Priority algorithms for graph optimization problems ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Remarks on proper conflict-free colorings of graphs ⋮ Unnamed Item ⋮ Hardness of Rainbow Coloring Hypergraphs ⋮ Recognizing DNA graphs is difficult.
This page was built for publication: On the hardness of approximating the chromatic number
