The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear

DOI10.1016/0012-365X(92)90691-8zbMath0776.05073OpenAlexW1968769959MaRDI QIDQ1201273

Alexander A. Razborov

Publication date: 17 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(92)90691-8

zbMATH Keywords

adjacency matrixchromatic number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Related Items

The corruption bound, log-rank, and communication complexity, Non-deterministic communication complexity with few witnesses, Eigenvalues of Cayley graphs, Some combinatorial-algebraic problems from complexity theory, Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank, On rank vs. communication complexity, On the ``log rank-conjecture in communication complexity, The chromatic number and rank of the complements of the Kasami graphs, Around the log-rank conjecture, Clique versus independent set, On the binary and Boolean rank of regular matrices, On order and rank of graphs, A counterexample to the Alon-Saks-Seymour conjecture and related problems, Matrix rank and communication complexity, On set intersection representations of graphs, The log-rank conjecture and low degree polynomials, Chromatic number and the 2-rank of a graph

Cites Work

• A counterexample to the rank-coloring conjecture
• Unnamed Item