Conditional Hardness for Approximate Coloring

DOI10.1137/07068062XzbMATH Open1192.68317OpenAlexW2047861934MaRDI QIDQ3575151FDOQ3575151

Oded Regev, Elchanan Mossel, Irit Dinur

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 (39)

• Title not available (Why is that?)
• 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?)
• On percolation and ‐hardness
• Hypergraph list coloring and Euclidean Ramsey theory
• Two generalizations of proper coloring: hardness and approximability
• Approximately coloring graphs without long induced paths
• Bounds on 2-query locally testable codes with affine tests
• Title not available (Why is that?)
• Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• The Quest for Strong Inapproximability Results with Perfect Completeness
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover
• 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
• Robust Factorizations and Colorings of Tensor Graphs
• Linear Index Coding via Semidefinite Programming
• Title not available (Why is that?)
• Bi-Covering: Covering Edges with Two Small Subsets of Vertices
• High dimensional Hoffman bound and applications in extremal combinatorics
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
• Kneser graphs are like Swiss cheese
• Coloring tournaments with few colors: algorithms and complexity
• Approximate graph colouring and the hollow shadow
• Query-Efficient Dictatorship Testing with Perfect Completeness
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
• Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
• Title not available (Why is that?)

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)