Conditional Hardness for Approximate Coloring
From MaRDI portal
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
(59)- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- High dimensional Hoffman bound and applications in extremal combinatorics
- Bounds on 2-query locally testable codes with affine tests
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- Conditional hardness for approximate coloring
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- Hypergraph list coloring and Euclidean Ramsey theory
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Improved inapproximability results for maximum k-colorable subgraph
- Deciding Relaxed Two-Colourability: A Hardness Jump
- On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
- Bi-covering: covering edges with two small subsets of vertices
- On percolation and \(\mathcal{NP}\)-hardness
- Kneser graphs are like Swiss cheese
- Query-efficient dictatorship testing with perfect completeness
- The quest for strong inapproximability results with perfect completeness
- scientific article; zbMATH DE number 7559121 (Why is no real title available?)
- Approximating the orthogonality dimension of graphs and hypergraphs
- Simultaneous max-cut is harder to approximate than max-cut
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Hypergraph removal lemmas via robust sharp threshold theorems
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- \(H\)-wise independence
- Rainbow coloring hardness via low sensitivity polymorphisms
- Linear index coding via semidefinite programming
- Linear index coding via semidefinite programming
- On the hardness of pricing loss-leaders
- Approximating the orthogonality dimension of graphs and hypergraphs
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Topology and Adjunction in Promise Constraint Satisfaction
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Two generalizations of proper coloring: hardness and approximability
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- Robust Factorizations and Colorings of Tensor Graphs
- Approximate graph colouring and the hollow shadow
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- Coloring tournaments with few colors: algorithms and complexity
- d-to-1 hardness of coloring 3-colorable graphs with o(1) colors
- On independent sets, 2-to-2 games and Grassmann graphs
- Small-set expansion in the Johnson graph
- An invariance principle for the multi-slice, with applications
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Approximate graph coloring and the crystal with a hollow shadow
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Injective hardness condition for PCSPs
- Stability of large rainbow intersecting families with product measure
- Semidefinite programming and linear equations vs. homomorphism problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Bounded degree nonnegative counting CSP
- Linearly ordered colourings of hypergraphs
- On rich 2-to-1 games
- Beyond PCSP (1-in-3, NAE)
- Undefinability of approximation of 2-to-2 games
- Parameterized saga of first-fit and last-fit coloring
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- New hardness results for low-rank matrix completion
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)
