Orthogonal representations over finite fields and the chromatic number of graphs

DOI10.1007/BF01261326zbMath0862.05040MaRDI QIDQ2563517

René Peeters

Publication date: 19 May 1997

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

chromatic numbercolorabilityNP-hardnessmatrixorthogonal representation

Mathematics Subject Classification ID

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^*