Orthogonal representations over finite fields and the chromatic number of graphs
From MaRDI portal
Publication:2563517
DOI10.1007/BF01261326zbMath0862.05040MaRDI QIDQ2563517
Publication date: 19 May 1997
Published in: Combinatorica (Search for Journal in Brave)
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Related Items
Bounding the Optimal Rate of the ICSI and ICCSI problem, On the subspace choosability in graphs, Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank, Local orthogonality dimension, Entanglement can increase asymptotic rates of zero-error classical communication over classical channels, Unnamed Item, Unnamed Item, Unnamed Item, Interval matrices: realization of ranks by rational matrices, Topological Bounds for Graph Representations over Any Field, On the equivalence between low-rank matrix completion and tensor rank, A new property of the Lovász number and duality relations between graph parameters, Linear Index Coding via Semidefinite Programming, Polynomial time algorithm for min-ranks of graphs with simple tree structures, Unnamed Item, Matrix completion and tensor rank, A unified construction of semiring-homomorphic graph invariants, Topological bounds on the dimension of orthogonal representations of graphs, The hat guessing number of graphs, Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint, Chromatic number and the 2-rank of a graph, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The ellipsoid method and its consequences in combinatorial optimization
- Some simplified NP-complete graph problems
- The sandwich theorem
- On the \(p\)-ranks of net graphs
- Orthogonal representations and connectivity of graphs
- Applications of matrix methods to the theory of lower bounds in computational complexity
- A comparison of the Delsarte and Lovász bounds
- The Complexity of Near-Optimal Graph Coloring
- On the Shannon capacity of a graph
- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
- Ranks of zero patterns and sign patterns*