Rank and chromatic number of a graph
Andreı̌ Kotlov · Journal of Graph Theory · 1997
It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23(1996), 185–189) that the number of vertices in a twin-free graph is where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is where $\Delta = 4/3 < \sqrt{2}$. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 1–8, 1997