scientific article; zbMATH DE number 7561683
From MaRDI portal
DOI10.4230/LIPIcs.MFCS.2019.39MaRDI QIDQ5092401
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1906.05005
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
semidefinite programminghardness of approximationorthogonality dimensionKneser and Schrijver graphsorthogonal representations of hypergraphs
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Kneser's conjecture, chromatic number, and homotopy
- On the hardness of approximating minimum vertex cover
- On the quantum chromatic number of a graph
- Extremal problems concerning Kneser-graphs
- n-tuple colorings and associated graphs
- The multichromatic numbers of some Kneser graphs
- Orthogonal representations and connectivity of graphs
- Topological bounds on the dimension of orthogonal representations of graphs
- The hardness of 3-uniform hypergraph coloring
- Orthogonal representations over finite fields and the chromatic number of graphs
- Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
- New approximation guarantee for chromatic number
- Hardness of Approximate Hypergraph Coloring
- Coloring 3-Colorable Graphs with Less than n 1/5 Colors
- Conditional Hardness for Approximate Coloring
- Two-query PCP with subconstant error
- Forbidden Intersections
- Improving the performance guarantee for approximate graph coloring
- Approximate graph coloring by semidefinite programming
- The Complexity of Near-Optimal Graph Coloring
- On the Shannon capacity of a graph
- New approximation algorithms for graph coloring
- The Minrank of Random Graphs
- Coloring bipartite hypergraphs
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Coloring -colorable graphs using relatively small palettes
- Reducibility among Combinatorial Problems
- Algebraic approach to promise constraint satisfaction
- On a Fractional Version of Haemers’ Bound
- Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
- New hardness results for graph and hypergraph colorings
- Linear Index Coding via Semidefinite Programming
- On the hardness of approximating the chromatic number
