The hardness of 3-uniform hypergraph coloring
From MaRDI portal
Publication:2368586
Not much is known about the hardness of the problem of approximate coloring of a hypergraph. The paper makes a step towards better understanding of the problem by proving that coloring a 3-uniform 2-colorable hypergraph with \(c\) colors is NP-hard for any constant \(c\). The proof is based on combining the layered PCP and Kneser graph and relies on high chromatic numbers of the Kneser graph and its induced subgraphs known as Schrijver graphs.
Recommendations
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- scientific article; zbMATH DE number 1305101
- Improved hardness of approximating chromatic number
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Approximate coloring of uniform hypergraphs
Cited in
(50)- On the complexity of SNP block partitioning under the perfect phylogeny model
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- Partitioning the vertices of a cubic graph into two total dominating sets
- Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions
- Parallel computations and committee constructions
- The complexity of properly learning simple concept classes
- Constructive generation of very hard 3-colorability instances
- An expected polynomial time algorithm for coloring 2-colorable 3-graphs
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- The complexity of vertex coloring problems in uniform hypergraphs with high degree
- Hardness of Approximate Hypergraph Coloring
- Simultaneous approximation of constraint satisfaction problems
- Decision Trees and Influences of Variables Over Product Probability Spaces
- scientific article; zbMATH DE number 1305101 (Why is no real title available?)
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Coloring Graphs with Constraints on Connectivity
- The quest for strong inapproximability results with perfect completeness
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Approximating the orthogonality dimension of graphs and hypergraphs
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Extremal problems in hypergraph colourings
- Hardness of rainbow coloring hypergraphs
- Rainbow coloring hardness via low sensitivity polymorphisms
- New hardness results for graph and hypergraph colorings
- Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs
- Approximating the orthogonality dimension of graphs and hypergraphs
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- CLAP: A New Algorithm for Promise CSPs
- Topology and Adjunction in Promise Constraint Satisfaction
- On the structure of the set of panchromatic colorings of a random hypergraph
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- Coloring tournaments with few colors: algorithms and complexity
- The complexity of promise SAT on non-Boolean domains
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Parallel repetition of k-player projection games
- A logarithmic approximation of linearly-ordered colourings
- Local consistency as a reduction between constraint satisfaction problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Linearly ordered colourings of hypergraphs
- On the complexity of symmetric vs. functional PCSPs
- Symmetric promise constraint satisfaction problems: beyond the Boolean case
- Beyond PCSP (1-in-3, NAE)
- Extended box clustering for classification problems
- Improved linearly ordered colorings of hypergraphs via SDP rounding
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Committee polyhedral separability: complexity and polynomial approximation
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring
This page was built for publication: The hardness of 3-uniform hypergraph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368586)
