A counterexample to the rank-coloring conjecture

DOI10.1002/JGT.3190130413zbMath0674.05029OpenAlexW2057661677WikidataQ123346984 ScholiaQ123346984MaRDI QIDQ3828021

Noga Alon, P. D. Seymour

Publication date: 1989

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190130413

zbMATH Keywords

hypergraphCayley grapheigenvaluesadjacency matrixchromatic numbercommunication complexityrank-coloring conjecture

Mathematics Subject Classification ID

Hypergraphs (05C65) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Related Items (17)

The corruption bound, log-rank, and communication complexity ⋮ 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 ⋮ Some relations among term rank, clique number and list chromatic number of a graph ⋮ 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 ⋮ The minimum semidefinite rank of a triangle-free graph ⋮ On order and rank of graphs ⋮ A counterexample to the Alon-Saks-Seymour conjecture and related problems ⋮ Matrix rank and communication complexity ⋮ The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear ⋮ Rank, term rank and chromatic number of a graph ⋮ On set intersection representations of graphs ⋮ Chromatic number and the 2-rank of a graph ⋮ Communication complexity and combinatorial lattice theory

This page was built for publication: A counterexample to the rank-coloring conjecture