Conditional Hardness for Approximate Coloring
From MaRDI portal
(Redirected from 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
(56)- Approximating the orthogonality dimension of graphs and hypergraphs
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Deciding Relaxed Two-Colourability: A Hardness Jump
- Simultaneous max-cut is harder to approximate than max-cut
- scientific article; zbMATH DE number 7561683 (Why is no real title available?)
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Injective hardness condition for PCSPs
- Bi-covering: covering edges with two small subsets of vertices
- Stability of large rainbow intersecting families with product measure
- Hypergraph list coloring and Euclidean Ramsey theory
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- Linearly ordered colourings of hypergraphs
- Two generalizations of proper coloring: hardness and approximability
- Bounded degree nonnegative counting CSP
- Bounds on 2-query locally testable codes with affine tests
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- Query-efficient dictatorship testing with perfect completeness
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- 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
- On rich 2-to-1 games
- Improved inapproximability results for maximum k-colorable subgraph
- On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- Beyond PCSP (1-in-3, NAE)
- d-to-1 hardness of coloring 3-colorable graphs with o(1) colors
- Robust Factorizations and Colorings of Tensor Graphs
- On percolation and \(\mathcal{NP}\)-hardness
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Small-set expansion in the Johnson graph
- On independent sets, 2-to-2 games and Grassmann graphs
- Hypergraph removal lemmas via robust sharp threshold theorems
- 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
- An invariance principle for the multi-slice, with applications
- Undefinability of approximation of 2-to-2 games
- Linear index coding via semidefinite programming
- Approximate graph coloring and the crystal with a hollow shadow
- scientific article; zbMATH DE number 7559121 (Why is no real title available?)
- Semidefinite programming and linear equations vs. homomorphism problems
- 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)
