On the Functions with Values in $[\alpha(G), \overline \chi(G)]$

Abstract

Let $$ {\cal B}(G) =\{X : X \in{\Bbb R}^{n \times n}, X=X^T, I \le X \le I+A(G)\} $$ and $$ {\cal C}(G) =\{X : X \in{\Bbb R}^{n \times n}, X=X^T, I-A(G) \le X \le I+A(G)\} $$ 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 {\cal C}(G)} {\rm rank}(X)$, $r_+(G)=\min_{X \in {\cal B}(G)} {\rm rank}(X)$. We have shown previously that for every graph $G$, $\alpha(G) \le r_+(G) \le \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$ doesn't 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$.