Conditional Hardness for Approximate Coloring

DOI10.1137/07068062XzbMATH Open1192.68317OpenAlexW2047861934MaRDI QIDQ3575151FDOQ3575151

Authors: Irit Dinur, Elchanan Mossel, Oded Regev 

Publication date: 7 July 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/07068062x

Recommendations

• Conditional hardness for approximate coloring
• Hardness of Approximate Hypergraph Coloring
• Complexity of conditional colorability of graphs
• On the hardness of approximating the chromatic number
• Complexity of conditional colourings with given template
• Two generalizations of proper coloring: hardness and approximability
• Hardness and inapproximability of convex recoloring problems
• Approximating the Interval Constrained Coloring Problem
• Approximate hypergraph coloring

zbMATH Keywords

graph coloringhardness of approximationunique games

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (40)

• Deciding Relaxed Two-Colourability: A Hardness Jump
• Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
• Simultaneous max-cut is harder to approximate than max-cut
• Title not available (Why is that?)
• Bi-covering: covering edges with two small subsets of vertices
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Hypergraph list coloring and Euclidean Ramsey theory
• New NP-hardness results for 3-coloring and 2-to-1 label cover
• Two generalizations of proper coloring: hardness and approximability
• Bounds on 2-query locally testable codes with affine tests
• Title not available (Why is that?)
• Query-efficient dictatorship testing with perfect completeness
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• Rainbow coloring hardness via low sensitivity polymorphisms
• On the hardness of pricing loss-leaders
• Linear index coding via semidefinite programming
• \(H\)-wise independence
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• Topology and Adjunction in Promise Constraint Satisfaction
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
• Improved inapproximability results for maximum \(k\)-colorable subgraph
• On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
• Robust Factorizations and Colorings of Tensor Graphs
• On percolation and \(\mathcal{NP}\)-hardness
• Hypergraph removal lemmas via robust sharp threshold theorems
• Title not available (Why is that?)
• High dimensional Hoffman bound and applications in extremal combinatorics
• Conditional hardness for approximate coloring
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• Kneser graphs are like Swiss cheese
• Coloring tournaments with few colors: algorithms and complexity
• Approximate graph colouring and the hollow shadow
• The quest for strong inapproximability results with perfect completeness
• Linear index coding via semidefinite programming
• Title not available (Why is that?)
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms

This page was built for publication: Conditional Hardness for Approximate Coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575151)