Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank (Q6071819): Difference between revisions

@@ Property / OpenAlex ID @@
+W4388671588
@@ Property / OpenAlex ID: W4388671588 / rank @@
+Normal rank
@@ Property / cites work @@
+The Shannon capacity of a union
@@ Property / cites work: The Shannon capacity of a union / rank @@
+Normal rank
@@ Property / cites work @@
+Local orthogonality dimension
@@ Property / cites work: Local orthogonality dimension / rank @@
+Normal rank
@@ Property / cites work @@
+Index Coding With Side Information
@@ Property / cites work: Index Coding With Side Information / rank @@
+Normal rank
@@ Property / cites work @@
+Algebraic Approach to Promise Constraint Satisfaction
+Normal rank
@@ Property / cites work @@
+Q5002681
@@ Property / cites work: Q5002681 / rank @@
+Normal rank
@@ Property / cites work @@
+New hardness results for graph and hypergraph colorings
+Normal rank
@@ Property / cites work @@
+Linear Index Coding via Semidefinite Programming
@@ Property / cites work: Linear Index Coding via Semidefinite Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Index Codes With Near-Extreme Rates
@@ Property / cites work: Optimal Index Codes With Near-Extreme Rates / rank @@
+Normal rank
@@ Property / cites work @@
+Conditional Hardness for Approximate Coloring
@@ Property / cites work: Conditional Hardness for Approximate Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
+Normal rank
@@ Property / cites work @@
+Coloring graphs with locally few colors
@@ Property / cites work: Coloring graphs with locally few colors / rank @@
+Normal rank
@@ Property / cites work @@
+On chromatic number of graphs and set-systems
@@ Property / cites work: On chromatic number of graphs and set-systems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3137188
@@ Property / cites work: Q3137188 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Near-Optimal Graph Coloring
@@ Property / cites work: The Complexity of Near-Optimal Graph Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Q5060749
@@ Property / cites work: Q5060749 / rank @@
+Normal rank
@@ Property / cites work @@
+On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
+Normal rank
@@ Property / cites work @@
+Q3931312
@@ Property / cites work: Q3931312 / rank @@
+Normal rank
@@ Property / cites work @@
+Some properties of line digraphs
@@ Property / cites work: Some properties of line digraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Arc colorings of digraphs
@@ Property / cites work: Arc colorings of digraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5870293
@@ Property / cites work: Q5870293 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of H-coloring
@@ Property / cites work: On the complexity of H-coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Hardness of Approximating Chromatic Number
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Coloring 3-Colorable Graphs with Less than             <i>n</i>             <sup>1/5</sup>             Colors
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating the chromatic number
+Normal rank
@@ Property / cites work @@
+On the Hardness of Approximating the Network Coding Capacity
+Normal rank
@@ Property / cites work @@
+Q4133994
@@ Property / cites work: Q4133994 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Shannon capacity of a graph
@@ Property / cites work: On the Shannon capacity of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs and Geometry
@@ Property / cites work: Graphs and Geometry / rank @@
+Normal rank
@@ Property / cites work @@
+Orthogonal representations and connectivity of graphs
+Normal rank
@@ Property / cites work @@
+Orthogonal representations over finite fields and the chromatic number of graphs
+Normal rank
@@ Property / cites work @@
+On the arc-chromatic number of a digraph
@@ Property / cites work: On the arc-chromatic number of a digraph / rank @@
+Normal rank
@@ Property / cites work @@
+n-tuple colorings and associated graphs
@@ Property / cites work: n-tuple colorings and associated graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Improved hardness for <i>H</i>-colourings of <i>G</i>-colourable graphs
+Normal rank
@@ Property / cites work @@
+Q3002782
@@ Property / cites work: Q3002782 / rank @@
+Normal rank