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