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

Using a noncomplete extended \(p\)-sum of graphs [see, e.g., Section 2.5 in the book by the reviewer, \textit{M. Doob} and \textit{H. Sachs}, Spectra of graphs. Theory and application (1980; Zbl 0458.05042)] the author constructs an infinite sequence of graphs \(G_ n\) in which \(\text{rk}(A(G_ n))\leq O(n^ 3)\) and \(\chi(G_ n)\geq\Omega(n^ 4)\), where \(A(G)\) is the adjacency matrix of \(G\), \(\text{rk}(M)\) is the rank of \(M\) and \(\chi(G)\) is the chromatic number of \(G\).