The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
From MaRDI portal
Publication:1201273
DOI10.1016/0012-365X(92)90691-8zbMath0776.05073OpenAlexW1968769959MaRDI QIDQ1201273
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
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
