On the functions with values in \([\alpha (G), \overline{\chi} (G)]\) (Q1883688)

Summary: Let \[ {\mathcal B}(G)=\bigl\{X:X\in\mathbb{R}^{n\times n},\;X= X^T,\;I\leq X\leq I+A(G)\bigr\} \] and \[ {\mathcal C}(G)=\bigl\{X:X\in \mathbb{R}^{n \times n}, \;X=X^T,\;I-A(G)\leq X\leq I+A(G)\bigr\} \] be classes of matrices associated with graph \(G\). Here \(n\) is the number of vertices in graph \(G\), and \(A(G)\) is the adjacency matrix of this graph. Denote \(r(G)=\min_{X\in {\mathcal C}(G)}\text{rank}(X)\), \(r_+ (G)= \min_{X \in {\mathcal B}(G)}\text{rank}(X)\). We have shown previously that for every graph \(G\), \(\alpha(G)\leq r_+(G)\leq\overline\chi(G)\) holds and \(\alpha(G) =r_+(G)\) implies \(\alpha(G)=\overline\chi(G)\). In this article we show that there is a graph \(G\) such that \(\alpha(G)=r(G)\) but \(\alpha(G)<\overline \chi (G)\). In the case when the graph \(G\) does not contain two chordless cycles \(C_4\) with a common edge, the equality \(\alpha(G) =r(G)\) implies \(\alpha(G)=\overline \chi(G)\). Corollary: The last statement holds for \(d(G)\) -- the minimal dimension of the orthonormal representation of the graph \(G\).