New hardness results for graph and hypergraph colorings
From MaRDI portal
(Redirected from Publication:5368748)
Recommendations
- The hardness of 3-uniform hypergraph coloring
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- Conditional hardness for approximate coloring
Cited in
(37)- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- Improved hardness of approximating chromatic number
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- The quest for strong inapproximability results with perfect completeness
- Vertex isoperimetry and independent set stability for tensor powers of cliques
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Dichotomy for symmetric Boolean PCSPs
- Approximating the orthogonality dimension of graphs and hypergraphs
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Rainbow coloring hardness via low sensitivity polymorphisms
- (2+)-Sat is NP-hard
- Some new hereditary classes where graph coloring remains NP-hard
- Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
- Approximating the orthogonality dimension of graphs and hypergraphs
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Topology and Adjunction in Promise Constraint Satisfaction
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- Robust Factorizations and Colorings of Tensor Graphs
- Approximate graph colouring and the hollow shadow
- Conditional dichotomy of Boolean ordered promise CSPs
- The complexity of promise SAT on non-Boolean domains
- Quantum advantage and CSP complexity
- 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
- Quantum advantage and CSP complexity
- Injective hardness condition for PCSPs
- Semidefinite programming and linear equations vs. homomorphism problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Linearly ordered colourings of hypergraphs
- Symmetries and complexity (invited talk)
- Conditional dichotomy of Boolean ordered promise CSPs
- Beyond PCSP (1-in-3, NAE)
- Aggregation of evaluations without unanimity
- On approximability of satisfiable k-CSPs: V
This page was built for publication: New hardness results for graph and hypergraph colorings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368748)
